重建二叉树

【原题】 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。 【思路】 今天捡起之前一直没有ac的一道题,这道题显然是用递归的方法求解。十分钟过去,没有调试,竟然就 通过了,也是神奇。仔细看了以前提交的多次不通过的代码,思路其实是一样的,主要在于长度,递归的起止位置要特别小心,已经作为根结点的index就不用包含在下一次的递归序列当中。最好以一个栗子来手动演示一下。

public class Solution {
   public TreeNode reConstructBinaryTreeCore(int[] pre,int preStart,int preEnd,
            int[] in,int inStart,int inEnd){
        if(preEnd-preStart<=0||inEnd<=inStart) return null;
        TreeNode root=new TreeNode(pre[preStart]);
        int mid=inStart;
        //以前序第一个结点为根结点,在中序序列中找到该节点的位置,即可以递归构建左右子树
        for(int i=inStart;i<inEnd;i++)
            if(in[i]==pre[preStart]){
                mid=i;break;
            }
        int leftLen=mid-inStart;
        int rightLen=inEnd-mid;
        root.left=reConstructBinaryTreeCore(pre,preStart+1,preStart+1+leftLen,in,inStart,mid);//递归构建左子树
        root.right=reConstructBinaryTreeCore(pre,preStart+leftLen+1,preEnd,in,mid+1,inEnd);//递归构建右子树
        return root;
    }
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if(pre.length!=in.length) return null;
        return reConstructBinaryTreeCore(pre,0,pre.length,in,0,in.length);

    }
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏机器学习从入门到成神

数据结构之判断一棵树是否为完全二叉树

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

531
来自专栏熊二哥

深入入门系列--Data Structure--04树

终于有机会重新回头学习一下一直困扰自身多年的数据结构了,赶脚棒棒哒。一直以来,对数据结构的掌握基本局限于线性表,稍微对树有一丢丢了解,而对于图那基本上就是不懂(...

1719
来自专栏向治洪

数据结构之二叉树

二叉树的定义: 二叉树是树形结构的一个重要类型。许多实际问题抽象出来的数据结构往往是二叉树的形式,即使是一般的树也能简单地转换为二叉树,而且二叉树的存储结构及...

1875
来自专栏我是东东强

常见算法之二叉树遍历

所谓遍历二叉树,就是遵从某种次序,顺着某一条搜索路径访问二叉树中的各个结点,使得每个结点均被访问一次,而且仅被访问一次。本文详细介绍了二叉树的前序(又称先序)、...

662
来自专栏猿人谷

二叉树的非递归遍历(递归和非递归)

二 叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是 递归定义,...

17010
来自专栏猿人谷

二叉树的遍历——递归和非递归

二 叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是 递归定义...

1878
来自专栏编程理解

数据结构(四):平衡二叉树(AVL树)

。影响时间复杂度的因素即为二叉树的高,为了尽量避免树中每层上只有一个节点的情况,这里引入平衡二叉树。

553
来自专栏向治洪

基本数据结构概念

一、线性结构 顺序存储线性表:将元素依次存储在地址连续的存储单元中,物理上相邻; 链式存储线性表:将元素按照逻辑顺序链接在依次,不要求地址连续; ...

1866
来自专栏C/C++基础

二叉树构建,先序,中序,后序遍历(以及非递归实现),广度优先遍历

二叉树是一类简单而又重要的树形结构,在数据的排序、查找和遍历方面有着广泛的应用。由于其清晰的结构,简单的逻辑,广泛的应用和大量的指针操作,在面试过程屡见不鲜,快...

431
来自专栏C/C++基础

判断二叉树是否为平衡二叉树

解题思路: 根据二叉树的定义,我们可以递归遍历二叉树的每一个节点来,求出每个节点的左右子树的高度,如果每个节点的左右子树的高度相差不超过1,按照定义,它就是...

592

扫码关注云+社区