POJ 2255：樹的恢復——從前序與中序遍歷構建後序遍歷

題目背景

給定一棵二叉樹的前序遍歷（根-左-右）和中序遍歷（左-根-右），樹中節點以唯一大寫字母標記（最多 26 個節點）。要求重建樹並輸出後序遍歷（左-右-根）。

輸入輸出格式

• 輸入：多組測試數據，每行包含兩個字符串 preord 和 inord，以 EOF 結束
• 輸出：每組對應一行後序遍歷字符串

樣例

輸入：
DBACEGF ABCDEFG
BCAD CBAD

輸出：
ACBFGED
CDAB

核心遞歸算法

1. 前序第一個字符為根節點
2. 在中序中定位根節點，左側為左子樹，右側為右子樹
3. 遞歸構建左右子樹
4. 後序輸出：先遞歸左、再遞歸右、最後訪問根

C++ 實現

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

struct Node {
    char data;
    Node *left, *right;
    Node(char c) : data(c), left(nullptr), right(nullptr) {}
};

char pre[100], in[100];

// 遞歸構建子樹
// preL: 前序起始索引, inL: 中序起始索引, len: 子樹長度
Node* build(int preL, int inL, int len) {
    if (len <= 0) return nullptr;
    char rootVal = pre[preL];
    Node* root = new Node(rootVal);
    int idx = strchr(in + inL, rootVal) - in; // 根在中序中的相對位置
    int leftLen = idx - inL;
    root->left  = build(preL + 1, inL, leftLen);
    root->right = build(preL + 1 + leftLen, idx + 1, len - 1 - leftLen);
    return root;
}

// 後序遍歷輸出
void postOrder(Node* root) {
    if (!root) return;
    postOrder(root->left);
    postOrder(root->right);
    cout << root->data;
}

int main() {
    while (cin >> pre >> in) {
        int len = strlen(pre);
        Node* root = build(0, 0, len);
        postOrder(root);
        cout << '\n';
        // 實際比賽中可略去釋放內存
    }
    return 0;
}

複雜度分析

• 時間：O(n²)（每次查找根節點掃描中序），n ≤ 26 完全足夠
• 空間：O(n) 遞歸棧

優化提示

可預先建立字符→中序索引的哈希表，將查找降為 O(1)，總時間 O(n)。但給定數據規模極小，簡單實現即可 AC。