k652. 二元搜尋樹復原 (BST) 題解

681 words

3 minutes

k652. 二元搜尋樹復原 (BST) 題解

2024-10-13

題解

資料結構

/

BST

/

二元樹

/

後序走訪

/

競程

/

C++

題目連結

問題敘述#

給定一棵二元搜尋樹 (BST) 的後序走訪序列，請重建這棵樹，並輸出每個節點的值 Ui 及其父節點 Fi（根為 -1），輸出時按 Ui 遞增排序。

BST 定義：

左子樹所有值 < 根
右子樹所有值 > 根
左右子樹也為 BST

後序走訪：左 → 右 → 根

範例: alt text

輸入格式#

第一行：正整數 $N \ (1 \leq N \leq 2 \times 10^5)$ ，節點數量
第二行： $N$ 個互不相同的正整數 $P_1, P_2, \dots, P_N \ (1 \leq P_i \leq 10^9)$ ，為後序走訪序列

輸出格式#

輸出 $N$ 行，第 $i$ 行為兩個整數 $U_i$ $F_i$ ：

$U_i$ ：節點值（保證 $U_1 < U_2 < \dots < U_N$ ）
$F_i$ ： $U_i$ 的父節點值，若為根節點則輸出 -1

範例輸入 1#

1
8
2
2 1 6 3 15 19 12 7

範例輸出 1#

範例輸入 2#

1
7
2
7 3 1 9 15 20 16

範例輸出 2#

範例輸入 3#

範例輸出 3#

1
2 -1

解法思路#

後序序列最後為根，因此我們可以從右到左處理序列，利用堆疊 (stack) 來維護「右子樹路徑」，從而找出每個節點的父節點。

核心邏輯#

後序走訪的最後一個是根，設為 -1（沒有父節點）
由右往左掃：
- 若當前值小於堆疊頂端，代表它在左子樹
- 若當前值大於堆疊頂端，pop 直到找到合適位置（右子樹邊界）
- 根據 pop 結果或堆疊頂端確定父節點

複雜度分析#

時間：O(N log N)（最後 map 排序）
空間：O(N)

完整程式碼（C++）#

1
#include <bits/stdc++.h>
2
using namespace std;
3

4
int main() {
5
    int n;
6
    cin >> n;
7
    vector<int> post_order(n);
8
    for (int i = 0; i < n; i++) {
9
        cin >> post_order[i];
10
    }
11

12
    map<int, int> parent_map;
13
    stack<int> st;
14

15
    // 最後一個是根
16
    parent_map[post_order[n - 1]] = -1;
17
    st.push(post_order[n - 1]);
18

19
    for (int i = n - 2; i >= 0; i--) {
20
        int current = post_order[i];
21
        int parent = -1;
22

23
        while (!st.empty() && st.top() < current) {  // BST: 左小右大
24
            parent = st.top();
25
            st.pop();
26
        }
27

28
        if (parent == -1 && !st.empty()) {
29
            parent = st.top();
30
        } else if (parent == -1) {
31
            assert(false); // 理論上不會發生
32
        }
33

34
        parent_map[current] = parent;
35
        st.push(current);
36
    }
37

38
    for (const auto &entry : parent_map) {
39
        cout << entry.first << " " << entry.second << '\n';
40
    }
41

42
    return 0;
43
}