題目
#

leetcode 105 - Construct Binary Tree from Preorder and Inorder Traversal (題目說明請點連結)

題目簡述
#

給兩個整數陣列 preorder 和 inorder，其中 preorder 是二元樹的前序遍歷，inorder 是同一棵樹的中序遍歷。
請建構並返回這棵二元樹。

範例
#

Example 1:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

graph TD; A[3] B[9] C[20] D[null] E[null] F[15] G[7] A --> B A --> C B --> D B --> E C --> F C --> G

Example 2:

Input: preorder = [-1], inorder = [-1]
Output: [-1]

解題思路
#

這題要求我們從前序遍歷和中序遍歷建構二元樹。我們可以使用遞迴的方法，通過前序遍歷確定根節點，然後在中序遍歷中找到根節點的位置來劃分左右子樹。

解法
#

使用 HashMap 儲存中序遍歷中每個值的位置，方便 O(1) 查找
使用前序遍歷的順序來建構節點（前序遍歷的第一個元素總是根節點）
在中序遍歷中找到根節點位置，劃分左右子樹
遞迴建構左子樹和右子樹
返回建構好的二元樹

步驟
#

初始化：
- 創建 HashMap 儲存中序遍歷的值和索引對應關係
- 初始化前序遍歷索引 preorderIndex = 0
遞迴建構：
- 從前序遍歷中取出根節點值
- 在中序遍歷中找到根節點位置
- 遞迴建構左子樹：範圍 [inLeft, inorderRootIndex-1]
- 遞迴建構右子樹：範圍 [inorderRootIndex+1, inRight]
返回結果：
- 返回建構好的二元樹根節點

例子說明
#

preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]

graph TD; A[3] B[9] C[20] D[15] E[7] A --> B A --> C C --> D C --> E

步驟	前序遍歷索引	根節點值	中序根節點位置	左子樹範圍	右子樹範圍	建構結果
初始化	0	-	-	-	-	開始建構
第 1 步	0	3	1	[0,0]	[2,4]	根節點 3
第 2 步	1	9	0	[]	[]	左子節點 9
第 3 步	2	20	3	[2,2]	[4,4]	右子節點 20
第 4 步	3	15	2	[]	[]	節點 20 的左子節點 15
第 5 步	4	7	4	[]	[]	節點 20 的右子節點 7

最終結果： [3,9,20,null,null,15,7]

建構過程說明：

步驟 1：前序遍歷第一個元素 3 是根節點，在中序遍歷中位置為 1
步驟 2：左子樹範圍 [0,0] 對應值 9，右子樹範圍 [2,4] 對應值 [15,20,7]
步驟 3：繼續遞迴建構左右子樹

完整程式碼
#

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 儲存中序遍歷中每個值的位置，方便 O(1) 查找
    Map<Integer, Integer> inorderMap = new HashMap<>();
    // 前序遍歷的當前索引
    int preorderIndex = 0;

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        // 先把 inorder 存成 map，方便 O(1) 找位置
        for (int i = 0; i < inorder.length; i++) {
            inorderMap.put(inorder[i], i);
        }
        
        // 開始遞迴建構二元樹
        return helper(preorder, 0, inorder.length - 1);
    }

    private TreeNode helper(int[] preorder, int inLeft, int inRight) {
        // 邊界條件：如果左邊界大於右邊界，返回 null
        if (inLeft > inRight) {
            return null;
        }

        // 從前序遍歷中取出根節點值
        int rootVal = preorder[preorderIndex++];
        TreeNode root = new TreeNode(rootVal);

        // 在中序遍歷中找到根節點的位置
        int inorderRootIndex = inorderMap.get(rootVal);

        // 遞迴建構左子樹：範圍 [inLeft, inorderRootIndex-1]
        root.left = helper(preorder, inLeft, inorderRootIndex - 1);
        // 遞迴建構右子樹：範圍 [inorderRootIndex+1, inRight]
        root.right = helper(preorder, inorderRootIndex + 1, inRight);

        return root;
    }
}