重建二叉树

【原题】 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{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 条评论
登录 后参与评论

相关文章

来自专栏JetpropelledSnake

Python入门之os.walk()方法

os.walk方法,主要用来遍历一个目录内各个子目录和子文件。 os.walk(top, topdown=True, onerror=None, followl...

2086
来自专栏ChaMd5安全团队

SQLI-LABS 更新帖(一)

docker搭建环境 请自己安装好docker,然后使用ubuntu:14.04的镜像 docker pull ubuntu:14.04 以下是pcat提供的...

3368
来自专栏Huramkin的归档库

Vim入门

Vim是坠吼的编辑器,是最适合软件开发使用的,但是使用Vim需要的命令成为了劝退的重要因素。

1051
来自专栏Laoqi's Linux运维专列

正则扩展练习

grep命令的-P选项: 最典型的用法是,匹配指定字符串之间的字符。 比如,我们想在一句话(Hello,my name is aming.)中匹配中间的一段字符...

3716
来自专栏BPM云

Cordova一些问题

1353
来自专栏大学生计算机视觉学习DeepLearning

c++ 常用的遍历,删除,分割等等文件处理函数代码实现

原文链接:https://www.cnblogs.com/DOMLX/p/9622851.html

952
来自专栏张戈的专栏

Linux:sed命令详解

1. 简介 sed 是非交互式的编辑器。它不会修改文件,除非使用 shell 重定向来保存结果。默认情况下,所有的输出行都被打印到屏幕上。 ? sed 编辑器逐...

3626
来自专栏Android

递归删除目录下全部文件

/** * 递归删除文件和文件夹 * * @param file * 要删除的根目录 */ private void Del...

18810
来自专栏蓝天

Shell 条件判断汇总

-b file            若文件存在且是一个块特殊文件,则为真 -c file            若文件存在且是一个字符特殊文件,则为真 -d ...

652
来自专栏北京马哥教育

shell脚本编程之终端打印

echo是用于终端打印的操作。默认情况下,echo在每次调用后添加一个换行符。 下面三条命令输出一样 html] view plain copy echo "...

2706

扫码关注云+社区