剑指Offer(4)--重建二叉树

文章目录

  • 题目
  • 思路
  • 代码

题目

输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。

思路


首先我们看上面的图片,首先数据保证了正确性,那么前序的第一个肯定是root节点,也就是1,那么我们需要在中序遍历中找到1的位置,左边就是这个root的左子树,右边就是root的右子树。

我们可以举个栗子:对根节点的左子树进行解析:

对右子树进行解析:

只需要不断递归即可,当边界左边大于右边的时候,则停止

代码

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode reConstructBinaryTree(int[] pre, int[] in) {
        if (pre == null || pre.length == 0 || in == null || in.length == 0) {
            return null;
        }
        TreeNode root = constructBinaryTree(pre, 0, pre.length - 1, in, 0, in.length-1);
        return root;
    }

    TreeNode constructBinaryTree(int[] pre, int startPre, int endPre, int[] in, int startIn, int endIn) {
        // 不符合条件直接返回null
        if (startPre > endPre || startIn > endIn) {
            return null;
        }
        // 构建根节点
        TreeNode root = new TreeNode(pre[startPre]);
        for (int index = startIn; index <= endIn; index++) {
            if (in[index] == pre[startPre]) {
                // 左子树
                root.left = constructBinaryTree(pre, startPre + 1, startPre + (index - startIn), in, startIn, index - 1);
                // 右子树
                root.right = constructBinaryTree(pre, (index - startIn) + startPre + 1, endPre, in, index + 1, endIn);
                break;
            }
        }
        return root;
    }
}

热门文章

暂无图片
编程学习 ·

Guns V4.0中的代码生成的使用

Guns V4.0的生成代码功能1.创建需要用的表,并在数据库中生成2.点击Guns中的代码生成3.运行生成的sql4.权限配置5.End 1.创建需要用的表,并在数据库中生成 创建自己的表 DROP TABLE IF EXISTS `book`; CREATE TABLE `book` (`id` int(11) NOT NULL AUTO_INCREMENT COMMENT 主键…
暂无图片
编程学习 ·

Linux 命令使用笔记【zcat】

zcat 命令zcat 命令用于不真正解压缩文件,就能显示压缩包中文件的内容的场合。语法zcat (选项)(参数)选项-S:指定 gzip 格式的压缩包的后缀。当后缀不是标准压缩包后缀时使用此选项;-c:将文件内容写到标注输出;-d:执行解压缩操作;-l:显示压缩包中文件的列表;-L:显示软…
暂无图片
编程学习 ·

MySQL 简洁速查手册

MySQL 速查手册 文章目录MySQL 速查手册0. 前言1. 开启/关闭数据库2. 数据库操作3. 数据表操作4. 字段操作5. 数据操作6. 运算符7. 高级查询(group by、having、order by、limit)8. 高级插入9. 高级删除10. 高级更新11. 联合查询12. 连接查询12.1 左外连接12.2 右外连接13. 子查…
暂无图片
编程学习 ·

电商新手做亚马逊要怎样开始?

"说到互联网创业,很多人的第一个想到的是淘宝,但是很多人并不清楚,经过十几年的发展淘宝已经很难再进入了,利润也是下降到了最低,很多的卖家都在寻找机会做转型,而你一个毫无经验的小白现在进入,基本可以说很难生存,近年来,我国的跨境电子商务进入迅猛的发展阶段,…
暂无图片
编程学习 ·

【阿里云】学生成长计划领取资格考试答案分享

云计算及云服务器入门 刚刚尝试了阿里云的高校学生计划,完成身份和学生认证后出现了需要测试才能领取,没想到凭感觉还拿到了90分,科一科四都能过了哈哈,下面是分享,希望后半年能把这种好资源利用起来,真正学点吃饭的东西,正确答案加粗显示。 选择题单选 1.SQL语言的功能…
暂无图片
编程学习 ·

例题 6-18 雕塑(Sculpture,ACM/ICPC NWERC 2008,UVa12171)

原题链接:https://vjudge.net/problem/UVA-12171 分类:图 备注:离散化;floodfill 紫书思路:利用离散化把三维图缩小,用floodfill求出外围空气体积和内表面积,总体积减去空气体积即所求体积,内表面积即所求表面积。 离散化知识参考:https://blog.csdn.net/tlonline/art…
暂无图片
编程学习 ·

在 Kudu 中集成 Hive Metastore

在启用 Kudu-HMS 集成之前,要确保 Kudu 和 HMS 现有表的视图一致。这可能需要重命名Kudu表以符合Hive命名约束。在启用与 Hive Metastore 集成之前应升级现有 Kudu 表。准备升级 在升级过程中,Kudu群集仍然可用。Kudu 和 Hive Metastore 中的表可能会更改或重命名。 可以使用…
暂无图片
编程学习 ·

跟汤老师学Java笔记:文件字节输入输出流

跟汤老师学Java笔记:文件字节输入输出流 完成:第一遍 1.文件字节输入流创建和常用方法有哪些? 创建:构造参数有字符串和File对象两种 方法: 方法:fis.read() 作用:读取一个字节,返回int类型的字节值,如果读取到末尾返回-1 方法:fis.close() 作用:输入流用了操作系统…
暂无图片
编程学习 ·

计算机网络基础,看完不怕面试

前言 计算机网络学习的核心内容就是网络协议的学习。网络协议是为计算机网络中进行数据交换而建立的规则、标准或者说是约定的集合。因为不同用户的数据终端可能采取的字符集是不同的,两者需要进行通信,必须要在一定的标准上进行。一个很形象地比喻就是我们的语言,我们大天朝…
暂无图片
编程学习 ·

Exception 的意义

Exception 的意义 文章目录Exception 的意义引言Exception 的语义自底向上的观点自顶向下的观点结论 引言 为什么程序设计语言要加入 Exception 机制?这个问题的答案或许不是那么显然。 Exception 常见于 “操作过程可能出现意外” 的场景。比如,试图打开文件时发现文件不存在…
暂无图片
编程学习 ·

面试之一句话简述volatile

volatile是轻量级的synchronized,他保证了可见性,底层的关键主要是LOCK指令,该指令有两个作用,一是强制把处理器缓存写回内存,二是一旦处理器缓存写回了内存,就让其他处理器上相同的缓存失效,这样的话,其他处理器想要修改某个被写回内存的变量,就得重新去内存取值,而…
暂无图片
编程学习 ·

C语言指针笔记

C语言指针 一.地址与指针变量 程序在执行过程中需要有内存来存储需要用到的数据和程序代码,它们都占据一些内存单元,地址是这些内存单元的编号,同时包括它所指向的数据的类型信息。因此,可以把地址形象化地称为"指针"。 但不要把地址和指针混为一个概念,地址是数…
暂无图片
编程学习 ·

不使用乘法、除法和mod,实现两数相除

被除数除数=商+余数 需要注意的问题:int 的范围是[-2^31,2^31-1],也就是【-2147483648,2147483647】,如果-2147483648/-1结果会超出int 范围。 除法,乘法和mod都不能使用,那可以使用加减,移位。 只需保留商即可 保证数据在int范围。电脑做二进制除法的时候,是让被除数连…
暂无图片
编程学习 ·

面试被问傻了,同事说不懂volatile关键字,由浅入深讲解volatile

面试被问傻了,同事说不懂volatile关键字,由浅入深讲解volatile前言随着互联网企业的兴起,对我们技术的要求也越来越高,很多时候企业又想省钱,又想发挥出机器的最大性能,真是累坏了程序员们。当然,想要适应社会的进步,程序员也要不断的给自己充电,但人能忘本,基础知识…
暂无图片
编程学习 ·

【剑指offer】——和为s的序列

文章目录1、和为s的两个数字2、和为s的连续正数序列 1、和为s的两个数字 1、题目要求 输入一个递增排序的数组和一个数字s,在数组中查找两个数,使得它们的和正好是s。如果有多对数字的和等于s,则输出任意一对即可。示例1: 输入:nums = [2,7,11,15], target = 9 输出:[2,7…
暂无图片
编程学习 ·

liunx-搭建hadoop(2.7.1)和使用

1.搭建 1.集群jdk安装 配置JDK环境变量在局域网中关闭防火墙 service iptables stop设置主机映射 1. 打开配置文件vim /etc/hosts 2. 内容192.168.80.111 server1192.168.80.112 server2192.168.80.110 server3配置SSH免密登录 1. 生成私钥ssh-keygen -t dsa -P -f ~/.ssh/id_…
暂无图片
编程学习 ·

SpringBoot的demo创建

SpringBoot的demo创建 springBoot项目的创建又多种方式本次就说一种比较简单的方式 选择Spring Initializr,点击确定(选择这种方式的创建,需要又网络环境,这相当于在spring.io官网下载demo) 这些看个人需求,进行修改,没有修改的可以直接下一步 这个界面是选取SpringBoot…