当前位置: 首页 > 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;外键约束…...

装饰模式(Decorator Pattern)重构java邮件发奖系统实战

前言 现在我们有个如下的需求&#xff0c;设计一个邮件发奖的小系统&#xff0c; 需求 1.数据验证 → 2. 敏感信息加密 → 3. 日志记录 → 4. 实际发送邮件 装饰器模式&#xff08;Decorator Pattern&#xff09;允许向一个现有的对象添加新的功能&#xff0c;同时又不改变其…...

Flask RESTful 示例

目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题&#xff1a; 下面创建一个简单的Flask RESTful API示例。首先&#xff0c;我们需要创建环境&#xff0c;安装必要的依赖&#xff0c;然后…...

【kafka】Golang实现分布式Masscan任务调度系统

要求&#xff1a; 输出两个程序&#xff0c;一个命令行程序&#xff08;命令行参数用flag&#xff09;和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽&#xff0c;然后将消息推送到kafka里面。 服务端程序&#xff1a; 从kafka消费者接收…...

《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)

CSI-2 协议详细解析 (一&#xff09; 1. CSI-2层定义&#xff08;CSI-2 Layer Definitions&#xff09; 分层结构 &#xff1a;CSI-2协议分为6层&#xff1a; 物理层&#xff08;PHY Layer&#xff09; &#xff1a; 定义电气特性、时钟机制和传输介质&#xff08;导线&#…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

NFT模式:数字资产确权与链游经济系统构建

NFT模式&#xff1a;数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新&#xff1a;构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议&#xff1a;基于LayerZero协议实现以太坊、Solana等公链资产互通&#xff0c;通过零知…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

C++ Visual Studio 2017厂商给的源码没有.sln文件 易兆微芯片下载工具加开机动画下载。

1.先用Visual Studio 2017打开Yichip YC31xx loader.vcxproj&#xff0c;再用Visual Studio 2022打开。再保侟就有.sln文件了。 易兆微芯片下载工具加开机动画下载 ExtraDownloadFile1Info.\logo.bin|0|0|10D2000|0 MFC应用兼容CMD 在BOOL CYichipYC31xxloaderDlg::OnIni…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

Java求职者面试指南:Spring、Spring Boot、MyBatis框架与计算机基础问题解析

Java求职者面试指南&#xff1a;Spring、Spring Boot、MyBatis框架与计算机基础问题解析 一、第一轮提问&#xff08;基础概念问题&#xff09; 1. 请解释Spring框架的核心容器是什么&#xff1f;它在Spring中起到什么作用&#xff1f; Spring框架的核心容器是IoC容器&#…...