從前序與中序遍歷序列重建二叉樹：遞歸演算法完整實作

從前序與中序遍歷序列重建二叉樹：遞歸演算法完整實作

題目

給定前序遍歷 pre[] = {1,2,4,5,3,6,7} 與中序遍歷 in[] = {4,2,5,1,6,3,7}，重建二叉樹。

核心原理

• 前序第一個元素為根節點
• 在中序中找到根節點，左側為左子樹，右側為右子樹
• 遞歸處理左右子樹

遞歸演算法步驟

1. 若序列為空返回 null
2. 建立根節點 root = new TreeNode(pre[preStart])
3. 在中序中定位根節點索引 inRootIndex
4. 左子樹節點數 leftSize = inRootIndex - inStart
5. 遞歸建立左子樹：前序 [preStart+1, preStart+leftSize]，中序 [inStart, inRootIndex-1]
6. 遞歸建立右子樹：前序 [preStart+leftSize+1, preEnd]，中序 [inRootIndex+1, inEnd]

Java 實作（索引版，避免陣列拷貝）

public class BinaryTreeReconstruction {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder == null || inorder == null || preorder.length != inorder.length) {
            return null;
        }
        return build(preorder, 0, preorder.length - 1, 
                     inorder, 0, inorder.length - 1);
    }

    private TreeNode build(int[] pre, int preL, int preR, 
                           int[] in, int inL, int inR) {
        if (preL > preR || inL > inR) return null;

        TreeNode root = new TreeNode(pre[preL]);
        int inRootIdx = inL;
        while (inRootIdx <= inR && in[inRootIdx] != pre[preL]) inRootIdx++;
        int leftSize = inRootIdx - inL;

        root.left = build(pre, preL + 1, preL + leftSize, in, inL, inRootIdx - 1);
        root.right = build(pre, preL + leftSize + 1, preR, in, inRootIdx + 1, inR);
        return root;
    }

    // 後序驗證
    public void postOrder(TreeNode root) {
        if (root == null) return;
        postOrder(root.left);
        postOrder(root.right);
        System.out.print(root.val + " ");
    }

    public static void main(String[] args) {
        int[] pre = {1,2,4,5,3,6,7};
        int[] in = {4,2,5,1,6,3,7};
        BinaryTreeReconstruction solver = new BinaryTreeReconstruction();
        TreeNode root = solver.buildTree(pre, in);
        solver.postOrder(root); // 輸出: 4 5 2 6 7 3 1
    }
}

class TreeNode {
    int val;
    TreeNode left, right;
    TreeNode(int x) { val = x; }
}

複雜度分析

• 時間：O(n) —— 每個節點訪問一次，中序查找可用 HashMap 優化至 O(1)
• 空間：O(h) —— 遞歸棧深度，h 為樹高（最壞 O(n)）

擴展

同理可從「中序 + 後序」重建，前序換為後序最後一個元素為根。