根据一棵树的两种遍历构造二叉树

题目
给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。
示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]
提示:
1 <= preorder.length <= 3000inorder.length == preorder.length-3000 <= preorder[i], inorder[i] <= 3000preorder和inorder均 无重复 元素inorder均出现在preorderpreorder保证 为二叉树的前序遍历序列inorder保证 为二叉树的中序遍历序列
前置知识:
preorder:前序遍历(Preorder Traversal 亦称先序遍历)——访问根结点--->根的左子树--->根的右子树。
inorder:中序遍历(Inorder Traversal)——根的左子树--->根节点--->根的右子树
前序遍历所得的第一个节点就是根节点,所以可以用来确定的是root根节点在中序遍历的位置,
再根据中序遍历,root根节点的左边是这棵二叉树的左树,root根节点的右边是这课二叉树的右树来构建这课二叉树
以示例1为例谈谈对题目的理解
示例1输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
preorder = [ 3, 9, 20, 15, 7 ] 3就为这棵二叉树的root根节点
inorder = [ 9, 3, 15, 20, 7 ] 9为root的左树,并且只有一个节点,所以9为root的左节点
15,20,7这三个节点为root的右树,再根据中序遍历根的左子树--->根节点--->根的右子树可得
root的右节点为20这个节点,20节点的左节点为15这个节点,右节点为7这个节点
画图演示上述文字说明

解题思路:
根据题目所给的前序遍历的节点顺序在中序遍历中进行递归来构建二叉树
1.根据前序遍历找到中序遍历根节点iRoot的位置,创建根节点,再确定iBegin,iEnd的位置,i++;
2.对iBegin和iEnd的位置进行判断,当iBegin>iEnd时,返回null,递归开始回退;
2.在中序遍历当中,根据iRoot ,iBegin,iEnd的位置,并进行左树和右树的构建;
对上述三步进行递归,递归完了之后,二叉树构建完成,返回根节点root
注:对前序遍历所得节点的利用才是本题代码的灵魂所在
图示:

解题代码
class Solution {public int i = 0;public TreeNode buildTree(int[] preorder, int[] inorder) {return create_a_binary_tree(preorder, inorder, 0, inorder.length - 1);}public TreeNode create_a_binary_tree(int[] preorder, int[] inorder, int inBegin, int inEnd) {if (inBegin > inEnd) {return null;//给定的数组int[] preorder, int[] inorder,遍历完了,没有子树了,该节点为空节点,返回null,递归开始回退}//先根据先序遍历创建根节点TreeNode root = new TreeNode(preorder[i]);//找到当前根节点,在中序遍历的位置int rootIndex = findIndex(inorder, inBegin, inEnd, preorder[i]);i++;//递归构建左树root.left = create_a_binary_tree(preorder, inorder, inBegin, rootIndex - 1);//递归构建右树root.right = create_a_binary_tree(preorder, inorder, rootIndex + 1, inEnd);//前序遍历完成,返回根节点return root;}private int findIndex(int[] inorder, int inBegin, int inEnd, int key) {for (int j = inBegin; j <= inEnd; j++) {if (inorder[j] == key) {return j;}}return -1;}
}
运行结果

题目链接
https://leetcode.cn/problems/construct-binary-tree-from-preorder-and-inorder-traversal/submissions/
举一翻三,再来一道
根据一棵树的中序遍历与后序遍历构造二叉树
给定两个整数数组
inorder和postorder,其中inorder是二叉树的中序历,postorder是同一棵树的后序遍历,请你构造并返回这颗 二叉树 。
示例 1:

输入:inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出:[3,9,20,null,null,15,7]
示例 2:
输入:inorder = [-1], postorder = [-1]
输出:[-1]
后序遍历(Postorder Traversal)——根的左子树--->根的右子树--->根节点。
创建根节点后,先创建右数,再创建左树
根据示例1进行讲解,下图是代码递归过程

随着代码的递归,二叉树随之构建的过程

解题代码
public class Solution {public int i = 0;public TreeNode buildTree(int[] inorder, int[] postorder) {i = postorder.length - 1;return create_a_binary_tree(postorder, inorder, 0, inorder.length - 1);}public TreeNode create_a_binary_tree(int[] postorder, int[] inorder, int inBegin, int inEnd) {if (inBegin > inEnd) {return null;//给定的数组int[] postorder, int[] inorder,遍历完了,没有子树了,该节点为空节点,返回null,递归开始回退}//先根据先序遍历创建根节点TreeNode root = new TreeNode(postorder[i]);//找到当前根节点,在中序遍历的位置int rootIndex = findIndex(inorder, inBegin, inEnd, postorder[i]);i--;//递归先构建右树root.right = create_a_binary_tree(postorder, inorder, rootIndex + 1, inEnd);//递归后构建左树root.left = create_a_binary_tree(postorder, inorder, inBegin, rootIndex - 1);//前序遍历完成,返回根节点return root;}private int findIndex(int[] inorder, int inBegin, int inEnd, int key) {for (int j = inBegin; j <= inEnd; j++) {if (inorder[j] == key) {return j;}}return -1;}
}
运行结果

题目链接:
https://leetcode.cn/problems/construct-binary-tree-from-inorder-and-postorder-traversal/submissions/
完结撒花✿✿ヽ(°▽°)ノ✿✿

相关文章:
根据一棵树的两种遍历构造二叉树
题目 给定两个整数数组 preorder 和 inorder ,其中 preorder 是二叉树的先序遍历, inorder 是同一棵树的中序遍历,请构造二叉树并返回其根节点。 示例 1: 输入: preorder [3,9,20,15,7], inorder [9,3,15,20,7] 输出: [3,9,20,null,null,…...
stack 、 queue的语法使用及底层实现以及deque的介绍【C++】
文章目录 stack的使用queue的使用适配器queue的模拟实现stack的模拟实现deque stack的使用 stack是一种容器适配器,具有后进先出,只能从容器的一端进行元素的插入与提取操作 #include <iostream> #include <vector> #include <stack&g…...
没学C++,如何从C语言丝滑过度到python【python基础万字详解】
大家好,我是纪宁。 文章将从C语言出发,深入介绍python的基础知识,也包括很多python的新增知识点详解。 文章目录 1.python的输入输出,重新认识 hello world,重回那个激情燃烧的岁月1.1 输出函数print的规则1.2 输入函…...
haproxy负载均衡
1、配置环境 作用环境windows测试 192.168.33.158 172.25.0.11 haproxy负载均衡haproxy:2.8.1,centos7172.25.0.31web服务器1--rs1Apache:2.4,redhat9172.25.0.32web服务器2--rs2Apache:2.4 , redhat9 2、…...
【数据结构】顺序队列模拟实现
💐 🌸 🌷 🍀 🌹 🌻 🌺 🍁 🍃 🍂 🌿 🍄🍝 🍛 🍤 📃个人主页 :阿然成长日记 …...
TiDB数据库从入门到精通系列之六:使用 TiCDC 将 TiDB 的数据同步到 Apache Kafka
TiDB数据库从入门到精通系列之六:使用 TiCDC 将 TiDB 的数据同步到 Apache Kafka 一、技术流程二、搭建环境三、创建Kafka changefeed四、写入数据以产生变更日志五、配置 Flink 消费 Kafka 数据 一、技术流程 快速搭建 TiCDC 集群、Kafka 集群和 Flink 集群创建 c…...
Spring对象装配
在spring中,Bean的执行流程为启动spring容器,实例化bean,将bean注册到spring容器中,将bean装配到需要的类中。 既然我们需要将bea装配到需要的类中,那么如何实现呢?这篇文章,将来阐述一下如何实…...
bigemap如何添加mapbox地图?
第一步 打开浏览器,找到你要访问的地图的URL地址,并且确认可以正常在浏览器中访问;浏览器中不能访问,同样也不能在软件中访问。 以下为常用地图源地址: 天地图: http://map.tianditu.gov.cn 包含&…...
python爬虫6:lxml库
python爬虫6:lxml库 前言 python实现网络爬虫非常简单,只需要掌握一定的基础知识和一定的库使用技巧即可。本系列目标旨在梳理相关知识点,方便以后复习。 申明 本系列所涉及的代码仅用于个人研究与讨论,并不会对网站产生不好…...
Linux查找命令
find find /dir -name filename 按名字查找 find . -name “*.c” 将当前目录及其子目录下所有文件后缀为 .c 的文件列出来 find . -type f 将当前目录及其子目录中的所有文件列出 find . -ctime 20 将当前目录及其子目录下所有最近 20 天内更新过的文件列出 find / -type f -…...
在 IntelliJ IDEA 中使用 Docker 开发指南
目录 一、IDEA安装Docker插件 二、IDEA连接Docker 1、Docker for Windows 连接 2、SSH 连接 3、Connection successful 连接成功 三、查看Docker面板 四、使用插件生成镜像 一、IDEA安装Docker插件 打开 IntelliJ IDEA,点击菜单栏中的 "File" -&g…...
【并发编程】自研数据同步工具的优化:创建线程池多线程异步去分页调用其他服务接口获取海量数据
文章目录 场景:解决方案 场景: 前段时间在做一个数据同步工具,其中一个服务的任务是调用A服务的接口,将数据库中指定数据请求过来,交给kafka去判断哪些数据是需要新增,哪些数据是需要修改的。 刚开始的设…...
python函数、运算符等简单介绍3(无顺序)
set(集合) 集合(set) -> 负责存储【不重复的数据】,并且是【无序存储】 的容器,主要用来去重和逻辑比较 set1 {1,2,3,4,58,7,4,1,2,3,5} print(set1) print(type(set1)) # 输出结果: {1, 2, 3, 4, 5, 7, 58} <…...
TCP服务器(套接字通信)
服务器 客户端 结果...
【智慧工地源码】:人工智能、BIM技术、机器学习在智慧工地的应用
智慧工地云平台是专为建筑施工领域所打造的一体化信息管理平台。通过大数据、云计算、人工智能、BIM、物联网和移动互联网等高科技技术手段,将施工区域各系统数据汇总,建立可视化数字工地。同时,围绕人、机、料、法、环等各方面关键因素&…...
使用python读Excel文件并写入另一个xls模版
效果如下: 原文件内容 转化后的内容 大致代码如下: 1. load_it.py #!/usr/bin/env python import re from datetime import datetime from io import BytesIO from pathlib import Path from typing import List, Unionfrom fastapi import HTTPExcep…...
债务人去世,债权人要求其妻女承担还款责任,法院支持吗
债务人去世,债权人要求其妻女承担还款责任,法院支持吗 2019年9月20日,老张以公司资金周转为由向好友任某先后借款合计40万。2022年8月27日老张出具还款承诺书,承诺2022年11月30日前归还本息(本息90万元)到…...
arcgis pro3.0-3.0.1-3.0.2安装教程大全及安装包下载
一. 产品介绍: ArcGIS Pro 这一功能强大的单桌面 GIS 应用程序是一款功能丰富的软件,采用 ArcGIS Pro 用户社区提供的增强功能和创意进行开发。 ArcGIS Pro 支持 2D、3D 和 4D 模式下的数据可视化、高级分析和权威数据维护。 支持通过 Web GIS 在一系列 …...
@RequestHeader使用
RequestHeader 请求头参数的设置 GetMapping("paramTest/requestHeader")public String requestHeaderTest(RequestHeader("name") String name){return name;} 在Postman的Headers中添加请求头参数,不过貌似不能加中文...
LabVIEW开发图像采集和基于颜色的隔离
LabVIEW开发图像采集和基于颜色的隔离 在当今的工业和工厂中,准确性和精度是决定特定行业生产力的两个重要关键点。为了优化生产力,各行各业正在从手动操作转向自动操作和控制。机器人技术在工业过程中的出现为人类提供了机械辅助。机器视觉在工业机器人…...
挑战杯推荐项目
“人工智能”创意赛 - 智能艺术创作助手:借助大模型技术,开发能根据用户输入的主题、风格等要求,生成绘画、音乐、文学作品等多种形式艺术创作灵感或初稿的应用,帮助艺术家和创意爱好者激发创意、提高创作效率。 - 个性化梦境…...
ES6从入门到精通:前言
ES6简介 ES6(ECMAScript 2015)是JavaScript语言的重大更新,引入了许多新特性,包括语法糖、新数据类型、模块化支持等,显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var…...
RocketMQ延迟消息机制
两种延迟消息 RocketMQ中提供了两种延迟消息机制 指定固定的延迟级别 通过在Message中设定一个MessageDelayLevel参数,对应18个预设的延迟级别指定时间点的延迟级别 通过在Message中设定一个DeliverTimeMS指定一个Long类型表示的具体时间点。到了时间点后…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...
Java - Mysql数据类型对应
Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...
2025 后端自学UNIAPP【项目实战:旅游项目】6、我的收藏页面
代码框架视图 1、先添加一个获取收藏景点的列表请求 【在文件my_api.js文件中添加】 // 引入公共的请求封装 import http from ./my_http.js// 登录接口(适配服务端返回 Token) export const login async (code, avatar) > {const res await http…...
今日科技热点速览
🔥 今日科技热点速览 🎮 任天堂Switch 2 正式发售 任天堂新一代游戏主机 Switch 2 今日正式上线发售,主打更强图形性能与沉浸式体验,支持多模态交互,受到全球玩家热捧 。 🤖 人工智能持续突破 DeepSeek-R1&…...
06 Deep learning神经网络编程基础 激活函数 --吴恩达
深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...
Java 二维码
Java 二维码 **技术:**谷歌 ZXing 实现 首先添加依赖 <!-- 二维码依赖 --><dependency><groupId>com.google.zxing</groupId><artifactId>core</artifactId><version>3.5.1</version></dependency><de…...
mac 安装homebrew (nvm 及git)
mac 安装nvm 及git 万恶之源 mac 安装这些东西离不开Xcode。及homebrew 一、先说安装git步骤 通用: 方法一:使用 Homebrew 安装 Git(推荐) 步骤如下:打开终端(Terminal.app) 1.安装 Homebrew…...
