重建二叉树

Python进击者

发布于 2019-09-17 15:09:18

3590

发布于 2019-09-17 15:09:18

文章被收录于专栏：JAVAandPython君

本文来自sunandstarws的csdn文章

博客地址：https://blog.csdn.net/sunandstarws/article/details/86578080

题目：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路：

看到这个题目就明白需要花点时间，上数据结构课的时候，明白了怎么根据前序和中序可以唯一确定一颗二叉树，并且也知道怎么重建，但是要用代码实现起来，还是有点困难，毕竟自己很久没有写了。我知道要实现那种思路，肯定需要借用递归或者归并。但是不是理的很清，后面觉得借鉴别人怎么实现的，看完之后，决定自己动手，最开始用java编写，写完之后，出现空指针异常和数组非法访问错误，与别人代码对了很久，最后终于找到错误了，这个题困了我一天。对于空指针异常，自己建立对象或者声明数组的时候最好还是初始化，不要等到后面才想起，数组非法访问是由于自己声明的数组太大，没有很严谨，导致我前面一直找不到自己错在哪，感觉没有越界，把数组大小严格改到题目要求所需之后，就提交成功了，可能之前写C语言写习惯了，没有注意这方面，以后还是严谨一点。用js代码实现比Java要方便很多，比较顺利，虽然也出现错误，但是解决了java坑之后，来解决Js的坑就快很多了；

对于这种题目，主要还是想清楚怎么用递归实现，注意细节

java实现代码：

public class Solution {
  
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
 
        int len=in.length;
        if(len==0)
            return null;
        TreeNode tree=new TreeNode(pre[0]);
        int i,temp=-1,j=0;
        for(i=0;i<len;i++){
            if(pre[0]==in[i]){
                temp=i;
                break;
            }
        }
         
    int[] left=new int[temp];
      int[] leftpre=new int[temp];
        for(i=0;i<temp;i++){
            left[i]=in[i];
            leftpre[i]=pre[i+1];
        }//左子树
     int[] right=new int[len-temp-1];
          int[] rightpre=new int[len-temp-1]; 
        for(i=temp+1;i<len;i++){
            right[j]=in[i];
            rightpre[j]=pre[i];
            j++;
        }//右子树
        tree.left=reConstructBinaryTree(leftpre,left);
        tree.right=reConstructBinaryTree(rightpre,right);
        return tree;
    }

JavaScript实现代码：

/* function TreeNode(x) {
    this.val = x;
    this.left = null;
    this.right = null;
} */
function reConstructBinaryTree(pre, vin)
{
      var len=vin.length;
        if(len==0)
            return null;
      var tree=new TreeNode(pre[0]);
        var i,temp=-1,j=0;
        for(i=0;i<len;i++){
            if(pre[0]==vin[i]){
                temp=i;
                break;
            }
        }
       var left=new Array(temp);
      var  leftpre=new Array(temp);
        for(i=0;i<temp;i++){
            left[i]=vin[i];
            leftpre[i]=pre[i+1];
        }//左子树
    var right=new Array(len-temp-1);
        var rightpre=new Array(len-temp-1); 
        for(i=temp+1;i<len;i++){
            right[j]=vin[i];
            rightpre[j]=pre[i];
            j++;
        }//右子树
        tree.left=reConstructBinaryTree(leftpre,left);
        tree.right=reConstructBinaryTree(rightpre,right);
    
        return tree;
    // write code here
}

本文参与腾讯云自媒体同步曝光计划，分享自微信公众号。

原始发表：2019-01-27，如有侵权请联系 cloudcommunity@tencent.com 删除

二叉树