本篇内容主要讲解“LeetCode题解之如何重建二叉树”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“LeetCode题解之如何重建二叉树”吧!
题目
输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如,给出
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:
3 / \ 9 20 / \ 15 7
题解
上周说过 前序遍历和后序遍历,其实这种前序、中序、后序都是相对于中间节点的处理顺序。
比如先序遍历的顺序就应该是:
[ 根节点 | 左子树 | 右子树 ]
同理,中序遍历的顺序就是:
[ 左子树 | 根节点 | 右子树 ]
所以前序遍历的第一个元素肯定就是 根节点。
然后,我们就能在 中序遍历找到根节点,并正确把中序遍历区分为三部分,也就是左子树中序、根节点、右子树中序。
举个例子:
如果只有三个元素,那么到这里就能结束了,因为树已经能画出来了。
比如前序是【3,9,20】,中序是【9,3,20】
我们根据中序知道了根节点3,然后在中序中就能区分出左子树节点9,根节点3,右子树节点20。
现在我们扩散开,如果不止3个节点呢?
举例2:
如果是5个元素,比如前序是[3,9,20,15,7],中序是[9,3,15,20,7]
经过第一次分割,我们把中序分成了左子树9,根节点3,右子树【15,20,7】
这时候,右子树该怎么分呢?跟节点是什么呢?又不知道了。
所以这时候要再联系到前序遍历,根据我们所知道的左子树节点,得出前序中右子树应该为【20,15,7】,所以右子树的根节点为20。
总之,就是前序和中序互相帮助,最终通过递归完成我们树的构建。
解法1
解法1就是依靠递归。
递归的过程就是找出每个父节点的左子树节点和右子树节点,一共三个值。
而最终的取值都是从前序列表中取值,其实就是取每个小树的父节点。
而中序遍历数组的作用就是找到 每次父节点在中序遍历数组中的位置。
得出如下算法。
class Solution { int[] preorder; HashMap<Integer, Integer> dic = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { this.preorder = preorder; for(int i = 0; i < inorder.length; i++) dic.put(inorder[i], i); return recur(0, 0, inorder.length - 1); } TreeNode recur(int root, int left, int right) { if(left > right) return null; //根节点 TreeNode node = new TreeNode(preorder[root]); //分割点 int i = dic.get(preorder[root]); node.left = recur(root + 1, left, i - 1); node.right = recur(root + i - left + 1, i + 1, right); return node; } }
其中每次取右子树的根节点需要注意:
左子树的节点数为i-left。
所以在前序遍历数组中,左子树的节点+根节点位置,就是左子树的最后一个节点位置,也就是root+i-left。
最后得出右子树的根节点为:root + i - left + 1
而递归的结束条件就是,左右子树节点相遇,也就是left>right。
时间复杂度
O(n),n为树的节点数量。
空间复杂度
O(N),用到了HashMap。
解法2
还有一种办法叫做迭代方法,这个方法挺巧妙的,当时也是看了很久的官方解答才想明白的,哈哈。
它的主要思想是理解前序遍历和中序遍历的规则,然后一个个从前序遍历中取值,并放到合适的位置。
比如以下这个二叉树:
3 / \ 9 20 / / \ 8 15 7 / \ 5 10 / 4
前序遍历,可以发现是首先把最左边的节点列出来,也就是 3,9,8,5,4
而中序列表是反着来的,从最左边的下面开始,往上列,如果发现某个节点有右子节点,就开始往右边列。
比如 4,5,8。这时候发现8有右子节点,那么就开始数 10 ,然后继续最左边往上,9,3。
最后列一下完整的前序和中序:
preorder = [3, 9, 8, 5, 4, 10, 20, 15, 7] inorder = [4, 5, 8, 10, 9, 3, 15, 20, 7]
总之,前序是从左边列开始,从上往下排。中序就是从左边列开始,从下往上排。
看看代码:
class Solution { public TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder == null || preorder.length == 0) { return null; } TreeNode root = new TreeNode(preorder[0]); Deque<TreeNode> stack = new LinkedList<TreeNode>(); stack.push(root); int inorderIndex = 0; for (int i = 1; i < preorder.length; i++) { int preorderVal = preorder[i]; TreeNode node = stack.peek(); if (node.val != inorder[inorderIndex]) { node.left = new TreeNode(preorderVal); stack.push(node.left); } else { while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) { node = stack.pop(); inorderIndex++; } node.right = new TreeNode(preorderVal); stack.push(node.right); } } return root; } }
if语句是为了找到左列最后一个节点,比如上述例子中的4。
while循环是当发现有右节点的时候,要找到右节点的父节点,然后添加进去。
到此,相信大家对“LeetCode题解之如何重建二叉树”有了更深的了解,不妨来实际操作一番吧!这里是编程网网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!