温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

怎样实现重建python二叉树

发布时间:2021-12-13 15:54:25 阅读:304 作者:柒染 栏目:大数据
Python开发者专用服务器限时活动,0元免费领,库存有限,领完即止! 点击查看>>

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

题目:

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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}

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

亿速云「云服务器」,即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘,价格低至29元/月。点击查看>>

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

原文链接:https://my.oschina.net/u/4016785/blog/4564260

AI

开发者交流群×