力扣105——從前序與中序遍歷序列構造二叉樹
- 2020 年 2 月 2 日
- 筆記
原題
根據一棵樹的前序遍歷與中序遍歷構造二叉樹。
注意: 你可以假設樹中沒有重複的元素。
例如，給出
前序遍歷 preorder = [3,9,20,15,7] 中序遍歷 inorder = [9,3,15,20,7]
返回如下的二叉樹：
3 / 9 20 / 15 7
原題url：https://leetcode-cn.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/
解題
這道題目，主要就是在於大家對於二叉樹這個數據結構的熟悉程度了，根據其前序遍歷和中序遍歷，推算出原本的二叉樹。
我們想想，如果不是寫代碼，只是通過手寫的話，我們是如何查找的，就用題目給出的例子：
- 根據前序遍歷，第一個一定是根節點，那麼 3 就是根節點。
- 從中序遍歷中尋找 3，在它左邊的，都是其左子樹上的節點，在它右邊的，都是其右子樹上的節點。
- 因為中序遍歷中，3 的左邊只有9，那麼 9 就是 3 的左子節點。
- 根據前序遍歷
先根然後左子節點，然後再右子節點的規律，3 、9 之後的 20 一定是 3 的右子節點。 - 20 在中序遍歷中，其左右兩邊就是 15 和 7，因此15 和 7 就分別是它的左右子節點。
根據上面的分析，你就可以畫出例子中的二叉樹了。
那麼我們尋找的順序是，先從前序遍歷的第一個節點開始，在中序遍歷中找出它的位置，其左右兩邊就是其左右子樹了，
接着從左子樹入手，前序遍歷根節點之後的兩個節點應該就是其左右子樹，但需要考慮沒有左右子樹的情況，然後再以其子樹為根，在中序遍歷中找其左右子樹。
需要注意的是，只有針對根節點，其左右子節點是在前序遍歷中緊跟着根節點的，其他都是有距離的，需要根據左子樹遞推。
接下來看看代碼：
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { int[] preorder; int[] inorder; // preorder中遍歷過的數量，這樣找完左子樹中的節點，剩下的第一個節點，必然是右子節點 int preorderIndex = 0; // key為inorder中的值，value為inorder中的下標 Map<Integer, Integer> inorderMap; public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder.length == 0) { return null; } TreeNode node = new TreeNode(preorder[0]); if (preorder.length == 1) { return node; } this.preorder = preorder; this.inorder = inorder; this.inorderMap = new HashMap<>(inorder.length * 4 / 3 + 1); for (int i = 0; i < inorder.length; i++) { this.inorderMap.put(inorder[i], i); } return generateNode(0, inorder.length); } /** * 尋找當前節點的左右子節點 * start：inorder里開始尋找的節點下標 * end：inorder里終止尋找的節點下標 * preorderIndex：當前節點在preorder中的下標 */ public TreeNode generateNode(int start, int end) { if (start >= end) { return null; } // 當前節點 int value = preorder[preorderIndex]; TreeNode node = new TreeNode(value); // 當前節點的值，在inorder中的下標 int inorderIndex = inorderMap.get(value); // 當前節點已經找到，尋找下一個節點。 // 因為會先去尋找左節點，當該節點左子樹中所有節點全部找完後，前序遍歷中，剩下節點的第一個節點，一定是該節點的右節點。 preorderIndex++; // 尋找左節點 node.left = generateNode(start, inorderIndex); // 尋找右節點 node.right = generateNode(inorderIndex + 1, end); return node; } }
提交OK，執行用時：3 ms，內存消耗：40.1 MB。
總結
以上就是這道題目我的解答過程了，不知道大家是否理解了。這道題目主要就是尋找規律，優化的話，可能就是利用 map 構造中序遍歷中節點值和順序的關係。
有興趣的話可以訪問我的博客或者關注我的公眾號，說不定會有意外的驚喜。
https://death00.github.io/
