LeetCode 構造二叉樹：前序+中序 / 後序+中序 遞歸解法

題目

1. Construct Binary Tree from Preorder and Inorder Traversal
2. Construct Binary Tree from Inorder and Postorder Traversal

給定兩種遍歷序列，重構二叉樹，假設無重複值。

核心思想：遞歸分治

以「前序+中序」為例：

• 前序第一個元素是根節點。
• 在中序中找到根節點，左側為左子樹中序，右側為右子樹中序。
• 左子樹節點數決定前序中左子樹區間，右子樹同理。
• 遞歸構建左右子樹，拼接返回根節點。

「後序+中序」類似，後序最後一個是根節點。

代碼實現：前序+中序

/**
 * Definition for binary tree
 * struct TreeNode { int val; TreeNode *left; *right; TreeNode(int x):val(x),left(NULL),right(NULL){} };
 */
class Solution {
public:
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        if (preorder.empty()) return nullptr;
        return build(preorder, inorder, 0, preorder.size()-1, 0, inorder.size()-1);
    }
private:
    TreeNode* build(vector<int>& pre, vector<int>& in,
                    int preL, int preR, int inL, int inR) {
        if (preL > preR) return nullptr;
        int rootVal = pre[preL];
        TreeNode* root = new TreeNode(rootVal);
        int inRootIdx = inL;
        while (in[inRootIdx] != rootVal) inRootIdx++;
        int leftSize = inRootIdx - inL;
        root->left = build(pre, in, preL+1, preL+leftSize, inL, inRootIdx-1);
        root->right = build(pre, in, preL+leftSize+1, preR, inRootIdx+1, inR);
        return root;
    }
};

代碼實現：後序+中序

class Solution {
public:
    TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) {
        if (postorder.empty()) return nullptr;
        return build(inorder, postorder, 0, inorder.size()-1, 0, postorder.size()-1);
    }
private:
    TreeNode* build(vector<int>& in, vector<int>& post,
                    int inL, int inR, int postL, int postR) {
        if (inL > inR) return nullptr;
        int rootVal = post[postR];
        TreeNode* root = new TreeNode(rootVal);
        int inRootIdx = inL;
        while (in[inRootIdx] != rootVal) inRootIdx++;
        int leftSize = inRootIdx - inL;
        root->left = build(in, post, inL, inRootIdx-1, postL, postL+leftSize-1);
        root->right = build(in, post, inRootIdx+1, inR, postL+leftSize, postR-1);
        return root;
    }
};

關鍵點總結

1. 遞歸終止條件：區間為空（L > R）。
2. 利用中序定位根節點，劃分左右子樹大小。
3. 根據子樹大小在前序/後序中劃分對應區間。
4. 時間複雜度 O(n^2)（查找根節點為線性），可用哈希表優化至 O(n)。
5. 空間複雜度 O(h)（遞歸棧），最壞 O(n)。