1. 題目

給定兩個整數數組 preorder 和 inorder ，其中 preorder 是二叉樹的先序遍歷， inorder 是同一棵樹的中序遍歷，請構造二叉樹并返回其根節點。

示例 1:

輸入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
輸出: [3,9,20,null,null,15,7]

示例 2:
輸入: preorder = [-1], inorder = [-1]
輸出: [-1]

2. 題解

/*** 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 {int[] preorder;HashMap<Integer, Integer> dic = new HashMap<>();public TreeNode buildTree(int[] preorder, int[] inorder) {this.preorder = preorder;for(int i = 0; i < inorder.length; i++)dic.put(inorder[i], i);return recur(0, 0, inorder.length - 1);}TreeNode recur(int root, int left, int right) {if (left > right) return null;                          // 遞歸終止TreeNode node = new TreeNode(preorder[root]);          // 建立根節點int i = dic.get(preorder[root]);                       // 劃分根節點、左子樹、右子樹node.left = recur(root + 1, left, i - 1);              // 開啟左子樹遞歸node.right = recur(root + i - left + 1, i + 1, right); // 開啟右子樹遞歸return node;                                           // 回溯返回根節點}
}

3. 題解

出自：105. 從前序與中序遍歷序列構造二叉樹（分治，清晰圖解）

1-6行：這是對TreeNode類的定義或者說結構體的定義，它是一棵二叉樹，其中每個節點最多有兩個子節點，一個左子節點和一個右子節點。如果沒有提供值、左子節點或右子節點，它們將默認為null。

8-10行：這些代碼定義了一個名為Solution的類，其中包含了一些與二叉樹相關的方法。這段代碼的主要功能是根據前序遍歷和中序遍歷結果來構建二叉樹。

9行：將輸入的前序遍歷數組賦值給成員變量preorder。

11-12行：創建一個HashMap dic，用于存儲中序遍歷的元素及其在中序遍歷中的索引。這樣可以根據中序遍歷結果定位根節點和左右子樹的位置。

14行：調用recur函數構建二叉樹。傳入參數0表示前序遍歷的第一個元素作為根節點，0和inorder.length - 1分別表示左邊界和右邊界，用于劃分中序遍歷結果。

23-44行：這是一個遞歸函數，用于根據前序遍歷結果構建二叉樹。該函數接受三個參數：root、left和right，分別代表前序遍歷的根節點索引、中序遍歷的左邊界和右邊界。

• 如果左邊界大于右邊界，表示無法繼續劃分子樹，返回null。
• 否則，創建一個新的TreeNode，值為preorder[root]（即前序遍歷的根節點）。
• 在HashMap dic中查找根節點的索引i，并將其設為左子樹和右子樹的中界。然后遞歸構建左右子樹。
• 最后返回當前處理的TreeNode。

在這段代碼中，我們使用了前序遍歷和中序遍歷來確定二叉樹的結構。在每一步中，我們根據前序遍歷結果找到根節點，然后在中序遍歷結果中劃分出左子樹和右子樹，并遞歸構建它們。這樣就可以從給定的前序遍歷和中序遍歷結果重建一棵二叉樹。