怎样实现重建python二叉树

今天就跟大家聊聊有关怎样实现重建python二叉树，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。

成都创新互联公司是一家专注于网站制作、成都网站建设与策划设计,城中网站建设哪家好?成都创新互联公司做网站,专注于网站建设10多年,网设计领域的专业建站公司;建站业务涵盖:城中等地区。城中做网站价格咨询:18982081108

题目：

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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           if(pre[0]==in[i]){
               temp=i;
               break;
           }
       }
       
   int[] left=new int[temp];
     int[] leftpre=new int[temp];
       for(i=0;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           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           if(pre[0]==vin[i]){
               temp=i;
               break;
           }
       }
      var left=new Array(temp);
     var  leftpre=new Array(temp);
       for(i=0;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           right[j]=vin[i];
           rightpre[j]=pre[i];
           j++;
       }//右子树
       tree.left=reConstructBinaryTree(leftpre,left);
       tree.right=reConstructBinaryTree(rightpre,right);
   
       return tree;
   // write code here
}

看完上述内容，你们对怎样实现重建python二叉树有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注创新互联行业资讯频道，感谢大家的支持。

网页题目：怎样实现重建python二叉树
转载注明：http://6mz.cn/article/pggcgs.html