劍指 Offer 面試題 6：重建二叉樹——前序+中序遍歷遞歸構建

經典面試題：給定二叉樹的前序遍歷與中序遍歷序列（無重複值），重建二叉樹並返回根節點。本文詳細拆解遞歸構建邏輯、索引計算細節、邊界條件處理，附完整 Java 實現與複雜度分析。

題目復述

輸入：
前序遍歷：{1, 2, 4, 7, 3, 5, 6, 8}
中序遍歷：{4, 7, 2, 1, 5, 3, 8, 6}

輸出：重建後的二叉樹根節點
      1
     / \
    2   3
   /   / \
  4   5   6
   \     /
    7   8

核心洞察

• 前序首元素 = 根節點：前序 根 → 左 → 右，第一個必是根。
• 中序根元素分割左右子樹：中序 左 → 根 → 右，根左側為左子樹，右側為右子樹。
• 遞歸子問題同構：左右子樹同樣滿足「前序首為根、中序根分割」特性，自然適用遞歸。

遞歸演算法步驟

1. 若前序/中序區間為空，返回 null。
2. 取前序區間首元素 rootVal 建立根節點。
3. 在中序區間掃描找到 rootVal 的索引 inIndex。
4. 左子樹節點數 = inIndex - inStart。
5. 遞歸構建左子樹：
   前序區間 [preStart+1, preStart+leftSize]
   中序區間 [inStart, inIndex-1]
6. 遞歸構建右子樹：
   前序區間 [preStart+leftSize+1, preEnd]
   中序區間 [inIndex+1, inEnd]
7. 返回根節點。

完整 Java 實現

public class ReconstructBinaryTree {

    public static class TreeNode {
        int val;
        TreeNode left, right;
        TreeNode(int v) { val = v; }
    }

    // 入口：檢驗輸入合法性
    public static TreeNode reConstruct(int[] preOrder, int[] inOrder) {
        if (preOrder == null || inOrder == null ||
            preOrder.length != inOrder.length || preOrder.length == 0) {
            return null;
        }
        return build(preOrder, 0, preOrder.length - 1,
                     inOrder, 0, inOrder.length - 1);
    }

    // 核心遞歸函數：[ps, pe] 前序區間，[is, ie] 中序區間
    private static TreeNode build(int[] pre, int ps, int pe,
                                  int[] in, int is, int ie) {
        if (ps > pe) return null; // 區間為空

        int rootVal = pre[ps];
        TreeNode root = new TreeNode(rootVal);

        // 在中序區間尋找根節點位置
        int inIndex = is;
        while (inIndex <= ie && in[inIndex] != rootVal) inIndex++;
        if (inIndex > ie) throw new IllegalArgumentException("Invalid traversals");

        int leftSize = inIndex - is; // 左子樹節點數

        root.left  = build(pre, ps + 1, ps + leftSize,     in, is,       inIndex - 1);
        root.right = build(pre, ps + leftSize + 1, pe,     in, inIndex + 1, ie);

        return root;
    }

    // 中序遍歷驗證
    public static void inOrderPrint(TreeNode root) {
        if (root == null) return;
        inOrderPrint(root.left);
        System.out.print(root.val + " ");
        inOrderPrint(root.right);
    }

    public static void main(String[] args) {
        int[] pre = {1,2,4,7,3,5,6,8};
        int[] in  = {4,7,2,1,5,3,8,6};
        TreeNode root = reConstruct(pre, in);
        inOrderPrint(root); // 輸出：4 7 2 1 5 3 8 6
    }
}

關鍵索引推導圖解

前序：[根] [左子樹 preSize] [右子樹]
       ps   ps+1        ps+leftSize   pe

中序：[左子樹] [根] [右子樹]
       is      inIndex    inIndex+1   ie

leftSize = inIndex - is

複雜度分析

• 時間：O(n) —— 每個節點被訪問一次，中序掃描總共 O(n)（可用 HashMap 優化至 O(1) 查找）。
• 空間：O(h) 遞歸棧深度，h 為樹高；最壞 O(n)（退化鏈表），平均 O(log n)。

優化：HashMap 加速中序查找

// 建構前預處理：值 → 中序索引
Map<Integer, Integer> inMap = new HashMap<>();
for (int i = 0; i < inOrder.length; i++) inMap.put(inOrder[i], i);

// 遞歸中 O(1) 獲取
int inIndex = inMap.get(rootVal);

邊界情況與錯誤輸入處理

• 空陣列 / 長度不一致 → 返回 null 或拋異常。
• 遍歷序列包含重複值 → 本題假設無重複；若有重複，需引入節點唯一標識（如記憶體地址）區分。
• 前序中序不匹配（找不到根） → 拋 IllegalArgumentException。

擴展：後序 + 中序重建

同理，後序 左 → 右 → 根，末尾為根；中序根分割左右。遞歸邏輯對稱，只需調整索引計算。

總結

重建二叉樹考察對遍歷特性的理解與遞歸拆解能力。掌握「前序找根、中序分左右、索引精確計算」三步法，配合 HashMap 優化查找，即可寫出高效、健壯的解法。建議練習：手寫後序+中序版本，並嘗試迭代法（棧模擬）避免遞歸棧溢出風險。