從先序與中序遍歷構造二叉樹：分治法與棧模擬兩種實現

問題描述

給定二叉樹的先序遍歷和中序遍歷序列（無重複元素），重構二叉樹並返回根節點。

方法一：分治遞歸（直觀但需拷貝數組）

1. 先序第一個元素為根。
2. 在中序中找到根，左側為左子樹中序，右側為右子樹中序。
3. 根據左右子樹大小，從先序中劃分出左/右子樹先序序列。
4. 遞歸構造左右子樹。

缺點：每層遞歸創建新 vector，導致記憶體超限（MLE）。

方法二：棧模擬（原地構造，O(N) 空間）

利用先序序列的「根-左-右」和中序的「左-根-右」特性：
- 用棧維護當前路徑上的祖先節點。
- 遍歷先序序列，若棧頂 ≠ 中序當前元素，則創建左孩子（flag=0）或右孩子（flag=1）入棧。
- 若棧頂 == 中序當前元素，彈出棧頂，標記 flag=1（下一個將作為右孩子）。
- 中序指針前進。
此法無需拷貝數組，單次遍歷構造完成。

棧模擬代碼（C++）

TreeNode* buildTree(vector& preorder, vector& inorder) {
    if (preorder.empty()) return nullptr;
    stack st;
    TreeNode* root = new TreeNode(preorder[0]);
    st.push(root);
    TreeNode* cur = root;
    int i = 1, j = 0; // preorder index, inorder index
    int flag = 0; // 0: expect left child, 1: expect right child
    while (i < preorder.size()) {
        if (!st.empty() && st.top()->val == inorder[j]) {
            cur = st.top(); st.pop();
            flag = 1; ++j;
        } else {
            TreeNode* node = new TreeNode(preorder[i++]);
            if (flag == 0) cur->left = node;
            else cur->right = node;
            cur = node;
            st.push(cur);
            flag = 0;
        }
    }
    return root;
}

複雜度對比

分治法：時間 O(N²)（查找根位置），空間 O(N²)（數組拷貝）。
棧模擬：時間 O(N)，空間 O(N)（棧深度）。

注意點

• 假設元素唯一，否則中序查找根位置有歧義。
• 棧模擬中 flag 狀態機正確處理左/右孩子轉換。
• LeetCode 105 同款題目，棧模擬可通過大數據測試。