立志用最少的代碼做最高效的表達

---

輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建該二叉樹。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數字。

例如，給出
前序遍歷 preorder = [3,9,20,15,7]
中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：
3
/ \
9 20
/ \
15 7

限制：

0 <= 節點個數 <= 5000

---

文章目錄

• 1. 儲備知識
• 2. 分析
• 3. 解法：遞歸實現
• 4. 一次優化：HashMap映射
• 5. 二次優化：傳遞位置參數而非復制數組
• 6.測試用例
• 7. 本題考點

---

1. 儲備知識

樹是一種在實際編程中經常遇到的數據結構。它的邏輯很簡單:除根節點之外每個節點只有一個父節點，根節點沒有父節點;除葉節點之外所有節點都有一個或多個子節點，葉節點沒有子節點。父節點和子節點之間用指針鏈接。

由于樹的操作會涉及大量的指針，因此與樹有關的面試題都不太容易。當面試官想考查應聘者在有復雜指針操作的情況下寫代碼的能力時，他往往會想到用與樹有關的面試題。

面試的時候提到的樹，大部分是二叉樹。所謂二叉樹是樹的一種特殊結構，在二叉樹中每個節點最多只能有兩個子節點。在二叉樹中最重要的操作莫過于遍歷，即按照某一順序訪問樹中的所有節點。通常樹有如下幾種遍歷方式。

前序遍歷:先訪問根節點，再訪問左子節點，最后訪問右子節點。圖中的二叉樹的前序遍歷的順序是10、6、4、8、14、12、16。
中序遍歷:先訪問左子節點，再訪問根節點，最后訪問右子節點。圖中的二叉樹的中序遍歷的順序是4、6、8、10、12、14、16。

后序遍歷:先訪問左子節點，再訪問右子節點，最后訪問根節點。圖中的二叉樹的后序遍歷的順序是4、8、6、12、16、14、10。

---

---

2. 分析

在二叉樹的前序遍歷序列中，第一個數字總是樹的根節點的值。但在中序遍歷序列中，根節點的值在序列的中間，左子樹的節點的值位于根節點的值的左邊，而右子樹的節點的值位于根節點的值的右邊。因此我們需要掃描中序遍歷序列，才能找到根節點的值。

如圖2.7所示，前序遍歷序列的第一個數字1就是根節點的值。掃描中序遍歷序列，就能確定根節點的值的位置。根據中序遍歷的特點，在根節點的值1前面的3個數字都是左子樹節點的值，位于1后面的數字都是右子樹節點的值。

由于在中序遍歷序列中，有3個數字是左子樹節點的值，因此左子樹共有3個左子節點。同樣，在前序遍歷序列中，根節點后面的3個數字就是3個左子樹節點的值，再后面的所有數字都是右子樹節點的值。這樣我們就在前序遍歷和中序遍歷兩個序列中分別找到了左、右子樹對應的子序列。

---

---

3. 解法：遞歸實現

class Solution {public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length;if(n == 0) return null;// 1、建立根節點TreeNode r = new TreeNode(preorder[0]);// 2、找根節點的左右節點，即在in中找pre的值int p = 0;while(inorder[p] != r.val) p++;// 3、分割 + 遞歸r.left = buildTree(Arrays.copyOfRange(preorder, 1, p+1), Arrays.copyOfRange(inorder, 0, p));r.right = buildTree(Arrays.copyOfRange(preorder, p+1, n), Arrays.copyOfRange(inorder, p+1, n));// 4、建樹成功，返回樹return r;}}

---

---

4. 一次優化：HashMap映射

由于解法1中每次查根節點時，都需要將數列遍歷一遍，因此考慮：

定義HashMap為成員變量， 并重新構造一個方法myBuildTree()，專門提供HashMap鍵值對的生成，而后調用BuildTree方法，實現遞歸。

通過map映射每個索引所在的位置，將查找索引的級數降低至O(1)

定義兩個方法的原因是：若將HashMap的映射生成定義在了方法內，每次遞歸都會重復進行HashMap映射的生成。

class Solution {// 定義為成員變量，這樣類中兩個方法都可以使用它private Map<Integer, Integer>indexMap;public TreeNode myBuildTree(int[] preorder, int[] inorder) {int n = preorder.length;if(n == 0) return null;// 1. 定義根節點TreeNode r = new TreeNode(preorder[0]);// 2、查找界限值 + 遞歸int p = indexMap.get(r.val);r.left = buildTree(Arrays.copyOfRange(preorder, 1, p+1), Arrays.copyOfRange(inorder, 0, p));r.right = buildTree(Arrays.copyOfRange(preorder, p+1, n), Arrays.copyOfRange(inorder, p+1, n));return r;}public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length;indexMap = new HashMap<Integer, Integer>();for(int i = 0; i < n; i++) {indexMap.put(inorder[i], i);}return myBuildTree(preorder, inorder);} }

---

---

5. 二次優化：傳遞位置參數而非復制數組

再次提交，發現耗時依然很高，仔細思考后發現，在源碼中，每次遞歸都需要進行兩次數組的復制，而每次復制的耗時為O(n)， 因此考慮：

取消數組的復制操作（copyOfRange()方法），改為使用邊界值(left, right)代替，再次降低時間復雜度。

class Solution3 {private Map<Integer, Integer> indexMap;public TreeNode myBuildTree(int[] preorder, int[] inorder, int preorder_left, int preorder_right, int inorder_left, int inorder_right) {if (preorder_left > preorder_right) {return null;}// 前序遍歷中的第一個節點就是根節點int preorder_root = preorder_left;// 在中序遍歷中定位根節點int inorder_root = indexMap.get(preorder[preorder_root]);// 先把根節點建立出來TreeNode root = new TreeNode(preorder[preorder_root]);// 得到左子樹中的節點數目int size_left_subtree = inorder_root - inorder_left;// 遞歸地構造左子樹，并連接到根節點// 先序遍歷中「從 左邊界+1 開始的 size_left_subtree」個元素就對應了中序遍歷中「從 左邊界 開始到 根節點定位-1」的元素root.left = myBuildTree(preorder, inorder, preorder_left + 1, preorder_left + size_left_subtree, inorder_left, inorder_root - 1);// 遞歸地構造右子樹，并連接到根節點// 先序遍歷中「從 左邊界+1+左子樹節點數目 開始到 右邊界」的元素就對應了中序遍歷中「從 根節點定位+1 到 右邊界」的元素root.right = myBuildTree(preorder, inorder, preorder_left + size_left_subtree + 1, preorder_right, inorder_root + 1, inorder_right);return root;}public TreeNode buildTree(int[] preorder, int[] inorder) {int n = preorder.length;// 構造哈希映射，幫助我們快速定位根節點indexMap = new HashMap<Integer, Integer>();for (int i = 0; i < n; i++) {indexMap.put(inorder[i], i);}return myBuildTree(preorder, inorder, 0, n - 1, 0, n - 1);} }

---

---

6.測試用例

• 普通二叉樹（完全二叉樹、不完全二叉樹）
• 特殊二叉樹（退化為鏈表的二叉樹、只有一個節點的二叉樹）
• 特殊輸入測試（空樹、錯誤用例）

---

---

7. 本題考點

• 考查應聘者對二叉樹前序遍歷和中序遍歷的理解程度
• 考查應聘者分析復雜問題的能力

總結

以上是生活随笔為你收集整理的剑指 Offer 07. 重建二叉树【千字分析，三种方法】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。