重建二叉树

本文来自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
}

原文发布于微信公众号 - JAVAandPython君(JAVAandPythonJun)

原文发表时间:2019-01-27

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

扫码关注云+社区

领取腾讯云代金券