LeetCode题解之重建二叉树

前言

成都创新互联主要从事成都网站建设、网站设计、网页设计、企业做网站、公司建网站等业务。立足成都服务靖西,10余年网站建设经验,价格优惠、服务专业,欢迎来电咨询建站服务:13518219792

今天继续二叉树相关的算法题

题目

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如，给出

前序遍历 preorder = [3,9,20,15,7]

中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：

 
 
 
 
    
  
  
  
  
  1.  3 
    2.   
  
  
  
  2.  / \ 
    3.   
  
  
  
  3. 9  20 
    4.   
  
  
  
  4.   /  \ 
    5.   
  
  
  
  5.  15   7 
    6.

题解

上周说过 前序遍历和后序遍历，其实这种前序、中序、后序都是相对于中间节点的处理顺序。

比如先序遍历的顺序就应该是：

[ 根节点 | 左子树 | 右子树 ]

同理，中序遍历的顺序就是：

[ 左子树 | 根节点 | 右子树 ]

所以前序遍历的第一个元素肯定就是 根节点。

然后，我们就能在 中序遍历找到根节点，并正确把中序遍历区分为三部分，也就是左子树中序、根节点、右子树中序。

举个例子:

如果只有三个元素，那么到这里就能结束了，因为树已经能画出来了。

比如前序是【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就是依靠递归。

递归的过程就是找出每个父节点的左子树节点和右子树节点，一共三个值。

而最终的取值都是从前序列表中取值，其实就是取每个小树的父节点。

而中序遍历数组的作用就是找到 每次父节点在中序遍历数组中的位置。

得出如下算法。

 
 
 
 
    
  
  
  
  
  1. /** 
    2.   
  
  
  
  2.  * Definition for a binary tree node. 
    3.   
  
  
  
  3.  * public class TreeNode { 
    4.   
  
  
  
  4.  *     int val; 
    5.   
  
  
  
  5.  *     TreeNode left; 
    6.   
  
  
  
  6.  *     TreeNode right; 
    7.   
  
  
  
  7.  *     TreeNode(int x) { val = x; } 
    8.   
  
  
  
  8.  * } 
    9.   
  
  
  
  9.  */ 
    10.   
  
  
  
  10. class Solution { 
    11.   
  
  
  
  11.     int[] preorder; 
    12.   
  
  
  
  12.     HashMap dic = new HashMap<>(); 
    13.   
  
  
  
  13.     public TreeNode buildTree(int[] preorder, int[] inorder) { 
    14.   
  
  
  
  14.         this.preorder = preorder; 
    15.   
  
  
  
  15.         for(int i = 0; i < inorder.length; i++) 
    16.   
  
  
  
  16.             dic.put(inorder[i], i); 
    17.   
  
  
  
  17.         return recur(0, 0, inorder.length - 1); 
    18.   
  
  
  
  18.     } 
    19.   
  
  
  
  19.     TreeNode recur(int root, int left, int right) { 
    20.   
  
  
  
  20.         if(left > right) return null;         
    21.   
  
  
  
  21.         //根节点                   
    22.   
  
  
  
  22.         TreeNode node = new TreeNode(preorder[root]);    
    23.   
  
  
  
  23.         //分割点     
    24.   
  
  
  
  24.         int i = dic.get(preorder[root]);         
    25.   
  
  
  
  25.         node.left = recur(root + 1, left, i - 1);  
    26.   
  
  
  
  26.         node.right = recur(root + i - left + 1, i + 1, right);  
    27.   
  
  
  
  27.         return node;       
    28.   
  
  
  
  28.     } 
    29.   
  
  
  
  29. } 
    30.

其中每次取右子树的根节点需要注意：

左子树的节点数为i-left。

所以在前序遍历数组中，左子树的节点+根节点位置，就是左子树的最后一个节点位置，也就是root+i-left。

最后得出右子树的根节点为：root + i - left + 1

而递归的结束条件就是，左右子树节点相遇，也就是left>right。

时间复杂度

O(n)，n为树的节点数量。

空间复杂度

O(N)，用到了HashMap。

解法2

还有一种办法叫做迭代方法，这个方法挺巧妙的，当时也是看了很久的官方解答才想明白的，哈哈。

它的主要思想是理解前序遍历和中序遍历的规则，然后一个个从前序遍历中取值，并放到合适的位置。

比如以下这个二叉树：

 
 
 
 
    
  
  
  
  
  1.         3 
    2.   
  
  
  
  2.        / \ 
    3.   
  
  
  
  3.       9  20 
    4.   
  
  
  
  4.      /  /  \ 
    5.   
  
  
  
  5.     8  15   7 
    6.   
  
  
  
  6.    / \ 
    7.   
  
  
  
  7.   5  10 
    8.   
  
  
  
  8.  / 
    9.   
  
  
  
  9. 4 
    10.

前序遍历，可以发现是首先把最左边的节点列出来，也就是 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]

总之，前序是从左边列开始，从上往下排。中序就是从左边列开始，从下往上排。

看看代码：

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2.   
  
  
  
  2.     public TreeNode buildTree(int[] preorder, int[] inorder) { 
    3.   
  
  
  
  3.         if (preorder == null || preorder.length == 0) { 
    4.   
  
  
  
  4.             return null; 
    5.   
  
  
  
  5.         } 
    6.   
  
  
  
  6.         TreeNode root = new TreeNode(preorder[0]); 
    7.   
  
  
  
  7.         Deque stack = new LinkedList(); 
    8.   
  
  
  
  8.         stack.push(root); 
    9.   
  
  
  
  9.         int inorderIndex = 0; 
    10.   
  
  
  
  10.         for (int i = 1; i < preorder.length; i++) { 
    11.   
  
  
  
  11.             int preorderVal = preorder[i]; 
    12.   
  
  
  
  12.             TreeNode node = stack.peek(); 
    13.   
  
  
  
  13.             if (node.val != inorder[inorderIndex]) { 
    14.   
  
  
  
  14.                 node.left = new TreeNode(preorderVal); 
    15.   
  
  
  
  15.                 stack.push(node.left); 
    16.   
  
  
  
  16.             } else { 
    17.   
  
  
  
  17.                 while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) { 
    18.   
  
  
  
  18.                     node = stack.pop(); 
    19.   
  
  
  
  19.                     inorderIndex++; 
    20.   
  
  
  
  20.                 } 
    21.   
  
  
  
  21.                 node.right = new TreeNode(preorderVal); 
    22.   
  
  
  
  22.                 stack.push(node.right); 
    23.   
  
  
  
  23.             } 
    24.   
  
  
  
  24.         } 
    25.   
  
  
  
  25.         return root; 
    26.   
  
  
  
  26.     } 
    27.   
  
  
  
  27. } 
    28.

if语句是为了找到左列最后一个节点，比如上述例子中的4。

while循环是当发现有右节点的时候，要找到右节点的父节点，然后添加进去。

大家可以手动试试，解法2确实不太好理解。

至少解法1的递归方法是要掌握的。

时间复杂度

O(n)

空间复杂度

O(n)

参考

https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/solution/

本文转载自微信公众号「码上积木」，可以通过以下二维码关注。转载本文请联系码上积木公众号。

网页标题：LeetCode题解之重建二叉树
网址分享：http://www.shufengxianlan.com/qtweb/news32/256182.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

网站导航知识

分类信息网

成都网站建设　　 　香港服务器空间　　 　微商城开发　　 　高端网站设计　　 　四川服务器托管　　 　软文营销　　 　德阳机房托管　　 　成都网站建设　　 　成都纯水机　　 　德阳电信服务器托管　　 　网站建设推广　　 　成都网站设计　　 　成都网站设计　　 　微信开发　　 　西云服务器托管　　 　川西大数据中心　　 　成都网站优化　　 　seo网络营销推广　　 　成都托管服务器　　 　网站设计