【leetcode C语言实现】剑指 Offer 07.重建二叉树

题目描述

输入某二叉树的前序遍历和中序遍历的结果,请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

例如,给出

前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]
返回如下的二叉树:

限制:

0 <= 节点个数 <= 5000

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof

解题思路

前序遍历的第一个节点即为该二叉树的根节点,其后分别是左子树节点和右子树节点,但是前序遍历无法区分左子树和右子树的分界;中序遍历的根节点在序列中间,根节点左侧为左子树节点,后侧为右子树节点,这样结合前序遍历和中序遍历的根节点可以把原始序列分别划分为左子树和右子树序列,同样,这两段序列可以按照前面一样的方法进行节点确认,最终能重建二叉树。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */


struct TreeNode* buildTree(int* preorder, int preorderSize, int* inorder, int inorderSize){
    if(preorderSize == 0)  return NULL;

    int index = 0; 
    struct TreeNode* pnode=malloc(sizeof(struct TreeNode));    
    pnode->val = preorder[0];
    while(index < inorderSize)
    {
        if(inorder[index] == preorder[0])  break;
        else index++;
    }
    pnode->left = buildTree(preorder + 1, index, inorder, index);
    pnode->right = buildTree(preorder + 1 + index, preorderSize - index - 1, inorder + index + 1, preorderSize - index - 1);

    return pnode;
}

执行结果

热门文章

暂无图片
编程学习 ·

终于等到你,飞凌嵌入式i.MX6ULL核心板如约而至!

自从 2016年初,我们推出了FETMX6UL-C 核心板后,其高性价比、丰富的功能、15年生命周期、高稳定性的多方面优势,受到了广大客户的一致好评,在电力、医疗、工控、 物联网、能源管理、光伏、环境监测等领域取得大规模应用。 在此基础上, 我们推出了 FETMX6UL-C的“双胞胎兄弟…
暂无图片
编程学习 ·

实战系列-Spring Cloud微服务中三把利器Feign、Hystrix、Ribbon

导语在之前的分享中分享过关于Fegin的底层实现原理,以及Spring Cloud OpenFegin的启动原理。在这次的分享中主要总结一下Spring Cloud 微服务架构的三把利器。对于Fegin、Hystrix、Ribbon三个组件来说它们之间是什么样的关系。怎么样综合使用等这些问题就是这次分享的内容文章…
暂无图片
编程学习 ·

C++排雷:16. #pragma warning的几种用法

#pragma warning只对当前文件有效(对于.h,对包含它的cpp也是有效的),而不是对整个工程的所有文件有效。当该文件编译结束,设置也就失去作用。 #pragma warning(push)是保存当前的编译器警告状态;#pragma warning(push, n) 存储当前报警设置,并设置报警级别为n。n为从1到…
暂无图片
编程学习 ·

前端适配问题总结

前端适配问题总结视口布局的优点:宽度和高度全部自动适应!再加上rem布局的字体适应,可以完美解决各种屏幕适配问题!1.vw:1vw等于视口宽度的1%。2.vh:1vh等于视口高度的1%。3.vmin:选取vw和vh中最小的那个。4.vmax:选取vw和vh中最大的那个。vh and vw:相对于视口的高度…
暂无图片
编程学习 ·

HBase环境搭建

前提 Hadoop环境 Zookeeper集群上传解压HBase压缩包 #解压hbase tar -zxvf hbase-0.98.12.1-hadoop2-bin.tar.gz#重命名 mv hbase-0.98.12.1-hadoop2 hbase-0.98#移动至/opt/spurce/目录下 mv hbase-0.98 /opt/source/修改配置文件 配置RegionServer,把集群节点添加到regionse…
暂无图片
编程学习 ·

GPU与深度学习

GPU与深度学习一.为什么深度学习要使用CPU 深度学习:深度学习是模拟人脑神经系统而建立的数学网络模型,最大特点是需要大数据来训练,也就需要大量的并行的重复计算。 GPU:CPU的全称是Central Processing Unit,GPU的全称是Graphics Processing Unit。在命名上,这两种器件…
暂无图片
编程学习 ·

面试官:小伙子,你给我说一下线程池的线程复用原理吧

前言 前两天和粉丝聊天的时候,粉丝问了我一个挺有意思的问题,说他之前在面试的时候被问到线程池的线程复用原理,当时我跟他简单的说了一下,没想到过了几天又来问我这个问题了,说他最近又被问到了这个问题…想了想,干脆写篇文章把这个东西讲清楚吧,满满的干货都放在下面了…
暂无图片
编程学习 ·

日志框架 SLF4j

是什么:SLF4J,即简单日志门面(Simple Logging Facade for Java),不是具体的日志解决方案,它只服务于各种各样的日志系统。按照官方的说法,SLF4J是一个用于日志系统的简单Facade,允许最终用户在部署其应用时使用其所希望的日志系统为什么:在java.util.logging, logback…
暂无图片
编程学习 ·

centos7 64位使用心得

一、安装宝塔面板 1、安装宝塔面板,安装方法去官网查询 2、修改默认路径,面板设置 - 默认建站目录和默认备份目录修改为: /home /home/backup二、安装云锁 1、安装最新版、提示Install Complete(安装完成),下面是安装运行代码。 wget https://download.yunsuo.com.cn/v3/…
暂无图片
编程学习 ·

智慧RFID工地人员定位-工地人员定位系统-新导智能

随着RFID技能的逐渐老练,RFID工地人员定位系统系在施工项目中越来越多地被运用到实践当中。尤其是在工地分布范围广,现场环境恶劣的项目施行现场,为了对施工现场进行安全规范办理,在施工项目应用根据RFID工地人员定位体系,能够实时监测各个施工现场的人员状况,统一办理,…
暂无图片
编程学习 ·

云管理服务AWS Organizations正式在AWS中国区域上线

近期, AWS中国(宁夏)区域(由西云数据运营)和AWS中国(北京)区域(由光环新网运营)正式上线了云管理服务AWS Organizations。作为一种管理服务,AWS Organizations可集中控制和管理多个AWS账户,无论是初创公司还是大型企业均可以使用,而不需要额外付费。随着企业或机构…
暂无图片
编程学习 ·

软件测试的基本流程

软件测试的基本流程 1. 测试需求分析阶段阅读需求 理解需求 主要就是对业务的学习 分析需求点 参与需求评审会议2. 测试计划阶段主要任务就是编写测试计划 参考软件需求规格说明书 项目总体计划,内容包括测试范围(来自需求文档),进度安排,人力物力的分配,整体测试策略的制…
暂无图片
编程学习 ·

win10查看端口进程占用

1、按 win+R,点击运行页面,写入cmd回车,点击命令行页面;2、使用命令查看端口,这里查看443端口;netstat -aon|findstr "443"3、在这里,大家可以看到,本地的433端口被PID为4452的进程占用了;4、然后,使用tasklist命令查看进程;tasklist|findstr "4452&…
暂无图片
编程学习 ·

硕彦博创李飞授-------计算机基础及C语言变量

一、计算机基础 计算机只能识别二进制; 1.存储单位 最小存储单位:bit(比特) ----- 存储 0和1 基本存储单位:byte(字节) ----- 1byte = 8bit 其他单位:理论上 1KB = 1024B 1MB = 1024KB 1GB= 1024MB 1TB = 1024 GB Ps: 工业上:1Gb = 1000Mb 2.数制位: 二进制:满2进1,…
暂无图片
编程学习 ·

有符号右移和无符号右移,傻傻分不清楚。

接上篇文章——位运算:2的幂 。本篇文章介绍一个简单的位运算——右移。计算机中数字都是以二进制的形式存储的,而位运算就是对数字的二进制表示进行操作。从节省硬件的角度出发(加法和减法都可以通过加法电路执行),二进制都是采用补码的形式表示,也就是每个有符号数字二…
暂无图片
编程学习 ·

UE4学习-添加机关并添加代码控制

文章目录添加机关代码编写给密室添加屋顶打印日志控制系统角色创建一个新游戏模式替换DefaultPawn添加抓取组件获取起点和终点物体拾取,碰撞属性设置今日完整代码 添加机关 首先向场景里面添加一个聚光源添加聚光源以后,可以对其属性进行修改,如图:然后需要给聚光源添加一个…
暂无图片
编程学习 ·

Ubuntu系统分区(待补充)

Ubuntu系统下一个分区工具是gparted。假设一共有60G空间,建议按照以下方式来分区: 分区之前,建议备份一下现有数据防止丢失: sudo su cd / tar -cvpzf /media/sda7/backup.tgz —exclude=/lost+found —exclude=/sys —exclude=/media /
暂无图片
编程学习 ·

wx.DateTime.ParseDate(‘yesterday‘)往前倒退一天

用wxpython写了个小程序,打开程序后要把工作日期往前倒退一天,看wx.DateTime的说明时,发现这个控件有强大的自动分析功能。官方原文如下:The date formatting and parsing functions convert wx.DateTime objects to and from text. The conversions to text are mostly tr…
暂无图片
编程学习 ·

LeetCode-Algorithms-[Easy]509. 斐波那契数

斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是: F(0) = 0, F(1) = 1 F(N) = F(N - 1) + F(N - 2), 其中 N > 1. 给定 N,计算 F(N)。 示例 1:输入:2 输出:1 解释:F(2) = F(1) + F…
暂无图片
编程学习 ·

大数据-java基础-第4章 while和do-while循环结构

1.循环的定义? 答: 循环就是在不停的干着同一件事情。 2.循环结构的特点? 答: 循环结构的特点是都存在循环条件和循环操作。 3.什么是while循环,while循环的特点是? 答: while循环为:while(循环条件){循环操作};当循环的条件为真是则执行循环操作,当条件为假时,结…