重建二叉树

简介: 重建二叉树


题目:


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


相关文章
|
小程序 开发工具 开发者
小程序vant-weapp-商品卡片列表
小程序vant-weapp-商品卡片列表
445 0
|
自然语言处理 API Python
LLaMA
【9月更文挑战第26天】
418 63
|
9月前
|
机器学习/深度学习 算法框架/工具 网络架构
深度学习中的正则化技术及其对模型性能的影响
本文深入探讨了深度学习领域中正则化技术的重要性,通过分析L1、L2以及Dropout等常见正则化方法,揭示了它们如何帮助防止过拟合,提升模型的泛化能力。文章还讨论了正则化在不同类型的神经网络中的应用,并指出了选择合适正则化策略的关键因素。通过实例和代码片段,本文旨在为读者提供关于如何在实际问题中有效应用正则化技术的深刻见解。
|
JavaScript 前端开发 Java
FFmpeg开发笔记(四十七)寒冬下安卓程序员的几个技术转型发展方向
IT寒冬使APP开发门槛提升,安卓程序员需转型。选项包括:深化Android开发,跟进Google新技术如Kotlin、Jetpack、Flutter及Compose;研究Android底层框架,掌握AOSP;转型Java后端开发,学习Spring Boot等框架;拓展大前端技能,掌握JavaScript、Node.js、Vue.js及特定框架如微信小程序、HarmonyOS;或转向C/C++底层开发,通过音视频项目如FFmpeg积累经验。每条路径都有相应的书籍和技术栈推荐,助你顺利过渡。
277 3
FFmpeg开发笔记(四十七)寒冬下安卓程序员的几个技术转型发展方向
|
SQL 数据库 索引
SQL 编程最佳实践简直太牛啦!带你编写高效又可维护的 SQL 代码,轻松应对数据库挑战!
【8月更文挑战第31天】在SQL编程中,高效与可维护的代码至关重要,不仅能提升数据库性能,还降低维护成本。本文通过案例分析探讨SQL最佳实践:避免全表扫描,利用索引加速查询;合理使用JOIN,避免性能问题;避免使用`SELECT *`,减少不必要的数据传输;使用`COMMIT`和`ROLLBACK`确保事务一致性;添加注释提高代码可读性。遵循这些实践,不仅提升性能,还便于后期维护和扩展。应根据具体情况选择合适方法并持续优化SQL代码。
206 0
|
SQL 存储 Java
4.2 SQL Server获取webshell及提权基础
4.2 SQL Server获取webshell及提权基础
247 0
|
监控 测试技术 UED
升级和维护老旧LabVIEW程序
升级和维护老旧LabVIEW程序
207 0
|
监控 Python
什么是WSGI,uwsgi和gunicorn在Python Web部署中起到什么作用?
**WSGI**是Python Web应用与服务器间的标准接口。**uwsgi**是实现WSGI的服务器,用于在不同服务器上高效部署应用。**gunicorn**是高性能的WSGI服务器,提供易用接口和进程管理功能。两者协同工作,作为桥梁连接应用与服务器,支持高并发和生产环境部署,提升性能和可靠性。配置因应用和环境而异,需按需调整。
517 2
|
Java 数据安全/隐私保护
Kafka-Eagle安装及使用简介
Kafka-Eagle安装及使用简介
1189 0
|
存储 C语言
头歌c语言实训项目-综合案例课外练习:学生成绩管理系统
头歌c语言实训项目-综合案例课外练习:学生成绩管理系统
408 0