ZeroJudge 解題筆記：c126. 00536 - Tree Recovery

作者：王一哲
日期：2026年3月18日


ZeroJudge 題目連結：c126. 00536 - Tree Recovery

解題想法

這題需要知道二元樹的結構及走訪的順序。前序走訪的順序為父節點、左子節點、右子節點，中序走訪的順序為左子節點、父節點、右子節點，後序走訪的順序為左子節點、右子節點、父節點。因此，從測資中讀到的前序走訪資料開頭就是根節點，測資中的中序走訪資料左側為根節點的左子樹，右側為根節點的右子樹。依照這樣的原則設計從前序走訪、中序走訪資料建立後序走訪資料的函式。

Python 程式碼

用字串儲存二元樹走訪的資料，用時間約為 7 ms，記憶體約為 2.8 MB，通過測試。

import sys

def build_tree(preorder, inorder):
    if not preorder or not inorder: return ""  # 如果沒有資料，回傳空字串
    root = preorder[0]  # 前序走訪開頭為根節點
    root_idx = inorder.find(root)  # 找到中序走訪資料中根節點的索引值
    left_inorder = inorder[:root_idx]  # 中序走訪資料中左子樹資料
    right_inorder = inorder[root_idx+1:]  # 中序走訪資料中右子樹資料
    left_preorder = preorder[1:1+len(left_inorder)]  # 前序走訪資料中左子樹資料
    right_preorder = preorder[1+len(left_inorder):]  # 前序走訪資料中右子樹資料
    left_postorder = build_tree(left_preorder, left_inorder)  # 遞迴，找左子樹後序走訪資料
    right_postorder = build_tree(right_preorder, right_inorder)  # 遞迴，找右子樹後序走訪資料
    return left_postorder + right_postorder + root  # 組合成答案

result = []
lines = sys.stdin.readlines()
for line in lines:
    if not line.strip(): continue
    result.append(f"{build_tree(*line.split())}\n")
sys.stdout.write("".join(result))

用串列儲存二元樹走訪的資料，用時間約為 7 ms，記憶體約為 2.8 MB，通過測試。

import sys

def build_tree(preorder, inorder):
    if not preorder or not inorder: return []  # 如果沒有資料，回傳空串列
    root = preorder[0]  # 前序走訪開頭為根節點
    root_idx = inorder.find(root)  # 找到中序走訪資料中根節點的索引值
    left_inorder = inorder[:root_idx]  # 中序走訪資料中左子樹資料
    right_inorder = inorder[root_idx+1:]  # 中序走訪資料中右子樹資料
    left_preorder = preorder[1:1+len(left_inorder)]  # 前序走訪資料中左子樹資料
    right_preorder = preorder[1+len(left_inorder):]  # 前序走訪資料中右子樹資料
    left_postorder = build_tree(left_preorder, left_inorder)  # 遞迴，找左子樹後序走訪資料
    right_postorder = build_tree(right_preorder, right_inorder)  # 遞迴，找右子樹後序走訪資料
    return left_postorder + right_postorder + [root]  # 組合成答案

result = []
lines = sys.stdin.readlines()
for line in lines:
    if not line.strip(): continue
    ans = "".join(build_tree(*line.split()))
    result.append(f"{ans}\n")
sys.stdout.write("".join(result))

C++ 程式碼

使用時間約為 1 ms，記憶體約為 304 kB，通過測試。

#include <iostream>
#include <string>
using namespace std;

string build_tree(string preorder, string inorder) {
    if (preorder.empty() || inorder.empty()) return "";
    char root = preorder[0];
    size_t root_idx = inorder.find(root);
    string left_inorder = inorder.substr(0, root_idx);
    string right_inorder = inorder.substr(root_idx+1);
    string left_preorder = preorder.substr(1, left_inorder.size());
    string right_preorder = preorder.substr(1+left_inorder.size());
    string left_postorder = build_tree(left_preorder, left_inorder);
    string right_postorder = build_tree(right_preorder, right_inorder);
    return left_postorder + right_postorder + root;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    string preorder, inorder;
    while(cin >> preorder >> inorder) {
        cout << build_tree(preorder, inorder) << "\n";
    }
    return 0;
}