当前位置: 首页 > news >正文

力扣106 从中序与后续遍历序列构造二叉树

文章目录

  • 题目描述
  • 解题思路
  • 代码


题目描述

给定两个整数数组 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]

提示:

1 <= inorder.length <= 3000
postorder.length == inorder.length
-3000 <= inorder[i], postorder[i] <= 3000
inorder 和 postorder 都由 不同 的值组成
postorder 中每一个值都在 inorder 中
inorder 保证是树的中序遍历
postorder 保证是树的后序遍历

解题思路

我感觉这道题的注释不是很好写的很清晰,建议先看一下另外一道题的思路:最大二叉树
然后回来再看这道题的注释就会清晰很多

代码

class Solution {public TreeNode buildTree(int[] inorder, int[] postorder) {return build(inorder,0, inorder.length-1,postorder,0, postorder.length-1);}//这个函数负责构造二叉树public TreeNode build(int[] inorder,int leftIndex,int rightIndex,int[] postorder,int postLeftIndex,int postRightIndex){//如果left坐标小于right坐标,则表明是一个空树,也是递归出口if (leftIndex>rightIndex||postLeftIndex>postRightIndex){return null;}//构造根节点TreeNode root  = new TreeNode(postorder[postRightIndex]);//找到根节点在中序遍历中的位置int rootIndex = 0;for (int i = leftIndex; i <= rightIndex; i++) {if (inorder[i]==root.val){rootIndex=i;break;}}//中序遍历中rootIndex-leftIndex表示左子树有多少个节点int lenOfLeft = rootIndex-leftIndex;//寻找左子树的根节点,最后一个参数表示左子树的后序遍历序列结束的位置TreeNode leftChild = build(inorder,leftIndex,rootIndex-1,postorder,postLeftIndex,postLeftIndex+lenOfLeft-1);//寻找右子树的根节点TreeNode rightChild = build(inorder,rootIndex+1,rightIndex,postorder,postLeftIndex+lenOfLeft,postRightIndex-1);//root分别指向左子树和右子树root.left = leftChild;root.right = rightChild;return root;}
}

相关文章:

力扣106 从中序与后续遍历序列构造二叉树

文章目录 题目描述解题思路代码 题目描述 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7], …...

数字逻辑-时序逻辑电路一

一、实验目的 &#xff08;1&#xff09;熟悉触发器的逻辑功能及特性。 &#xff08;2&#xff09;掌握集成D和JK触发器的应用。 &#xff08;3&#xff09;掌握时序逻辑电路的分析和设计方法。 二、实验仪器及材料 三、实验内容及步骤 1、用D触发器&#xff08;74LS74&am…...

web 课程

文章目录 格式图片超链接书签链接表格例子横跨束跨 格式 <br /> <br/> #换行图片 <img> 标签是用于在网页中嵌入图像的 HTML 标签&#xff0c;它有一些属性可以用来控制图像的加载、显示和交互。以下是对 <img> 标签常用属性的详细介绍&#xff1a;…...

工业园区智慧水电设备管控系统

在现代工业园区中&#xff0c;水电设备的管控系统起着至关重要的作用。这些系统不仅仅是简单的机械装置&#xff0c;它们更是一种智慧的结合&#xff0c;为工业生产提供了可靠的保障和高效的管理。让我们一起来探索工业园区智慧水电设备管控系统的奥秘。 我们来看看水电设备的…...

Git之版本回退

文章转载于&#xff1a;https://www.jianshu.com/p/3020740561a8 以前&#xff0c;如果是要去除某一块功能&#xff0c;我都是选择性删除&#xff0c;选择性注释&#xff0c;然后前后逻辑各种查看&#xff0c;各种比较。每一次&#xff0c;改完这些我总感觉心好累啊&#xff01…...

「jQuery系列」jQuery 校验表单(Validate)

文章目录 一、校验表单&#xff08;Validate&#xff09;1. 基本用法2. 验证规则3. 国际化4. 插件扩展 二、Validate常用方法1. 基本验证2. 自定义验证规则3. 远程验证&#xff08;通过 AJAX&#xff09;4. 提交处理&#xff08;submitHandler&#xff09;5. 忽略某些元素的验证…...

【Java设计模式】十九、中介者模式

文章目录 1、中介者模式2、案例3、总结 1、中介者模式 如图&#xff1a; 同事类之间关联较多时&#xff0c;整体出现网状结构&#xff0c;耦合度极高。一个对象一变动&#xff0c;好多对象都得改。若变为右边的星形结构&#xff0c;则一个类的变动&#xff0c;只影响自身与中介…...

这个学习Python的神仙网站,后悔没早点发现

Python 作为时下最流行的编程语言&#xff0c;很多初学者都将它作为自学编程的首选。不管是有编程经验的开发者&#xff0c;还是新手小白&#xff0c;在这个 AIGC 时代&#xff0c; Python 都可以带你探索新世界。 入门 Python 绝非难事&#xff0c;但如何让自己坚持学下去是如…...

牛津大学“领域驱动设计”课程

领域驱动设计&#xff08;“DDD”&#xff09;是一种专注于系统领域而不是技术的软件设计方法。重点是构建共享的心理模型并以尽可能简单的方式在代码中表示该领域模型。数据库存储、框架等技术细节被认为是设计的次要方面。该模块将重点关注 DDD 和一般设计以及相关主题&#…...

Redisson分布式锁解决方案

官方地址 官网: https://redisson.org github: https://github.com/redisson/redisson 基于setnx实现的分布式锁存在的问题 redisson分布式锁原理 不可重入: 利用hash结构记录线程id和重入次数不可重试: 利用信号量和PubSub功能实现等待、唤醒, 获取锁失败的重试机制超时释放…...

linux命令深入研究——cat

cat命令&#xff0c;“猫”&#xff0c;可以理解为瞄一眼文件内容&#xff0c;其中可以用重定向符号对文件进行一些修改&#xff0c;如增加&#xff0c;删除文件内容&#xff0c;其命令参数如-n&#xff0c;-s&#xff0c;-b可以输出带有行号的行 如果想要快速删除文件内容&…...

代码随想录算法训练营第40天|343. 整数拆分、96.不同的二叉搜索树

343. 整数拆分 题目链接&#xff1a;link 文章讲解&#xff1a;link 视频讲解&#xff1a;link 一、做题感受&第一想法 其实第一反应是回溯……但感觉每层的集合都会很繁琐 二、学习文章后收获 1.动态规划思路 动规五要素分析 dp和i的定义&#xff1a;dp[i]指把i拆分后最…...

二叉树算法

递归序 每个节点都能回到3次! 相当于2执行完然后返回了代码会往下走,来到3节点 小总结: 也就是4节点先来到自己一次,不会执行if,先调用自己左边的那个函数,但是是null,直接返回。 这个函数执行完了,就会回到自己,调用自己右边的那个函数,结果又是空,又返回,回到…...

【2024年5月备考新增】《软考真题分章练习(答案解析) - 4 项目范围管理(高项)》

点击跳转无答案版 1、() includes the processes required to ensure that the project includes all the work required , and only the work required , to complete the project successfully . Managing the project scope is primarily concerned with defining and con…...

Docker拉取镜像存储不足

在使用Docker时&#xff0c;我们经常遇到一个问题&#xff0c;就是拉取镜像时提示存储空间不足。这是因为Docker在拉取镜像时需要将镜像文件下载到本地存储中&#xff0c;而有时本地存储空间不足以容纳完整的镜像文件。 本文将介绍一些解决这个问题的方法&#xff0c;并提供相…...

JUNIT5+Mockito单元测试

文章目录 1、前言2、Maven依赖2.1 JDK21SpringBoot版本基于3.1.02.2 JDK17SpringBoot版本基于2.2.5.RELEASE 3、业务代码4、单元测试 1、前言 之前写过一篇使用testMe自动生成单元测试用例&#xff0c;使用的是junit4来编写的单元测试用例&#xff0c;目前很多新项目都已经使用…...

【C#】【SAP2000】读取SAP2000中所有Frame对象的应力比到Grasshopper中

if (build true) {// 连接到正在运行的 SAP2000// 使用 System.Runtime.InteropServices.Marshal.GetActiveObject 方法获取正在运行的 SAP2000 实例cOAPI mySapObject (cOAPI)System.Runtime.InteropServices.Marshal.GetActiveObject("CSI.SAP2000.API.SapObject"…...

一台服务器部署两个独立的mysql实例

&#x1f341;博主简介&#xff1a; &#x1f3c5;云计算领域优质创作者 &#x1f3c5;2022年CSDN新星计划python赛道第一名 &#x1f3c5;2022年CSDN原力计划优质作者 &#x1f3c5;阿里云ACE认证高级工程师 &#x1f3c5;阿里云开发者社区专…...

SpringBoot(Lombok + Spring Initailizr + yaml)

1.Lombok 1.基本介绍 2.应用实例 1.pom.xml 引入Lombok&#xff0c;使用版本仲裁 <!--导入springboot父工程--><parent><artifactId>spring-boot-starter-parent</artifactId><groupId>org.springframework.boot</groupId><version&g…...

数据库基础知识超详细解析~‍(进阶/复习版)

文章目录 前言一、数据库的操作1.登入数据库2.创建数据库3.显示当前数据库4.使用数据库5.删除数据库 二、常用数据类型三、数据库的约束1约束类型2NULL约束3UNIQUE:唯一约束4DEFAULT&#xff1a;默认值约束5 PRIMARY KEY&#xff1a;主键约束6 FOREIGN KEY&#xff1a;外键约束…...

反向工程与模型迁移:打造未来商品详情API的可持续创新体系

在电商行业蓬勃发展的当下&#xff0c;商品详情API作为连接电商平台与开发者、商家及用户的关键纽带&#xff0c;其重要性日益凸显。传统商品详情API主要聚焦于商品基本信息&#xff08;如名称、价格、库存等&#xff09;的获取与展示&#xff0c;已难以满足市场对个性化、智能…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

根据万维钢·精英日课6的内容,使用AI(2025)可以参考以下方法:

根据万维钢精英日课6的内容&#xff0c;使用AI&#xff08;2025&#xff09;可以参考以下方法&#xff1a; 四个洞见 模型已经比人聪明&#xff1a;以ChatGPT o3为代表的AI非常强大&#xff0c;能运用高级理论解释道理、引用最新学术论文&#xff0c;生成对顶尖科学家都有用的…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

以光量子为例,详解量子获取方式

光量子技术获取量子比特可在室温下进行。该方式有望通过与名为硅光子学&#xff08;silicon photonics&#xff09;的光波导&#xff08;optical waveguide&#xff09;芯片制造技术和光纤等光通信技术相结合来实现量子计算机。量子力学中&#xff0c;光既是波又是粒子。光子本…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

为什么要创建 Vue 实例

核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...

Pydantic + Function Calling的结合

1、Pydantic Pydantic 是一个 Python 库&#xff0c;用于数据验证和设置管理&#xff0c;通过 Python 类型注解强制执行数据类型。它广泛用于 API 开发&#xff08;如 FastAPI&#xff09;、配置管理和数据解析&#xff0c;核心功能包括&#xff1a; 数据验证&#xff1a;通过…...

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡 背景 我们以建设星云智控官网来做AI编程实践&#xff0c;很多人以为AI已经强大到不需要程序员了&#xff0c;其实不是&#xff0c;AI更加需要程序员&#xff0c;普通人…...

链式法则中 复合函数的推导路径 多变量“信息传递路径”

非常好&#xff0c;我们将之前关于偏导数链式法则中不能“约掉”偏导符号的问题&#xff0c;统一使用 二重复合函数&#xff1a; z f ( u ( x , y ) , v ( x , y ) ) \boxed{z f(u(x,y),\ v(x,y))} zf(u(x,y), v(x,y))​ 来全面说明。我们会展示其全微分形式&#xff08;偏导…...