力扣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/
