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