LeetCode 筆記：從前序與中序遍歷構造二叉樹

題目要求

給定二叉樹的前序遍歷和中序遍歷，重建二叉樹。假設樹中無重複值。

遞歸構造原理

• 前序第一個元素為根節點。
• 在中序中找到根節點，左側為左子樹，右側為右子樹。
• 遞歸處理左右子樹，利用迭代器範圍傳遞子數組。

時間空間複雜度

每次在中序中查找根節點 O(n)，共 n 個節點，總時間 O(n²)。空間複雜度 O(1) 額外空間（不計遞歸棧）。

參考代碼

struct TreeNode {
    int val;
    TreeNode *left, *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

class Solution {
    TreeNode* build(vector<int>::iterator preB, vector<int>::iterator preE,
                    vector<int>::iterator inB,  vector<int>::iterator inE) {
        if (preB == preE) return NULL;
        int rootVal = *preB;
        TreeNode* root = new TreeNode(rootVal);
        auto inRoot = find(inB, inE, rootVal);
        if (inRoot != inE) {
            root->left = build(preB+1, preB + (inRoot - inB) + 1, inB, inRoot);
        }
        root->right = build(preB + (inRoot - inB) + 1, preE, inRoot+1, inE);
        return root;
    }
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty()) return NULL;
        return build(preorder.begin(), preorder.end(), inorder.begin(), inorder.end());
    }
};

優化方向

可用哈希表預存中序值到索引映射，將查找降為 O(1)，總時間優化至 O(n)。