一、題目描述給定一棵二叉樹的前序遍歷preorder和中序遍歷inorder請還原這棵二叉樹。題目保證數組中沒有重復元素。preorder [3, 9, 20, 15, 7] inorder [9, 3, 15, 20, 7]構造結果如下3 / \ 9 20 / \ 15 7關鍵是從兩種遍歷序列中確定根節點并劃分左右子樹。二、前序找根中序分左右先回顧遍歷順序前序遍歷根 - 左 - 右 中序遍歷左 - 根 - 右前序遍歷的第一個元素3是根節點。在中序遍歷中找到3[9, 3, 15, 20, 7] ↑ 根節點根節點左邊的[9]屬于左子樹右邊的[15,20,7]屬于右子樹。左子樹只有一個節點因此可以同步劃分前序遍歷左子樹preorder [9]inorder [9] 右子樹preorder [20,15,7]inorder [15,20,7]兩個子問題與原問題結構相同因此可以遞歸構造從前序遍歷中取出當前根節點在中序遍歷中找到根節點的位置遞歸構造左子樹遞歸構造右子樹。三、完整 Java 代碼class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { int len preorder.length; if (len 0) { return null; } TreeNode root new TreeNode(preorder[0]); // 找到根節點在中序遍歷中的索引位置,這個值也是左子樹的所有元素個數 int rootInInorder indexOf(inorder, preorder[0]); // 前序遍歷中左子樹的部分和右子樹的部分 int[] preLeft Arrays.copyOfRange(preorder, 1, 1 rootInInorder); // 復制是左閉右開區間 int[] preRight Arrays.copyOfRange(preorder, 1 rootInInorder, len); // 中序遍歷中左子樹的部分和右子樹的部分 int[] inLeft Arrays.copyOfRange(inorder, 0, rootInInorder); int[] inRight Arrays.copyOfRange(inorder, 1 rootInInorder, len); // 遞歸構建左右子樹 root.left buildTree(preLeft, inLeft); root.right buildTree(preRight, inRight); return root; } // 返回 x 在 a 中的下標保證 x 一定在 a 中 private int indexOf(int[] a, int x) { for (int i 0; ; i) { if (a[i] x) { return i; } } } }四、常見錯誤1. 把中序遍歷的第一個元素當成根節點根節點由前序遍歷確定中序遍歷只負責劃分左右區域。2. 先構造右子樹全局指針按“根、左、右”移動必須先遞歸左子樹。3. 區間沒有排除根節點正確邊界為root.left build(inorderLeft, rootIndex - 1); root.right build(rootIndex 1, inorderRight);