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

LeetCode 热题 100 105. 从前序与中序遍历序列构造二叉树

LeetCode 热题 100 | 105. 从前序与中序遍历序列构造二叉树

大家好,今天我们来解决一道经典的二叉树问题——从前序与中序遍历序列构造二叉树。这道题在 LeetCode 上被标记为中等难度,要求根据给定的前序遍历和中序遍历序列,构造并返回二叉树的根节点。


问题描述

给定两个整数数组 preorderinorder,其中 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 <= 3000
  • inorder.length == preorder.length
  • -3000 <= preorder[i], inorder[i] <= 3000
  • preorderinorder 均无重复元素
  • inorder 均出现在 preorder
  • preorder 保证为二叉树的前序遍历序列
  • inorder 保证为二叉树的中序遍历序列

解题思路

核心思想
  1. 前序遍历

    • 前序遍历的第一个元素是根节点。
    • 使用前序遍历的第一个元素在中序遍历中找到根节点的位置,从而将中序遍历分为左子树和右子树。
  2. 递归构造

    • 递归地构造左子树和右子树。

Python代码实现

class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:if not preorder or not inorder:return None# 前序遍历的第一个元素是根节点root_val = preorder[0]root = TreeNode(root_val)# 在中序遍历中找到根节点的位置mid_idx = inorder.index(root_val)# 递归构造左子树和右子树root.left = self.buildTree(preorder[1:mid_idx + 1], inorder[:mid_idx])root.right = self.buildTree(preorder[mid_idx + 1:], inorder[mid_idx + 1:])return root

代码解析

  1. 基本情况

    • 如果 preorderinorder 为空,直接返回 None
  2. 构造根节点

    • 使用 preorder 的第一个元素作为根节点的值。
  3. 找到根节点在中序遍历中的位置

    • 使用 inorder.index(root_val) 找到根节点在中序遍历中的位置。
  4. 递归构造左子树和右子树

    • 使用中序遍历的分割点,递归地构造左子树和右子树。
  5. 返回根节点

    • 返回构造好的根节点。

复杂度分析

  • 时间复杂度:O(n),其中 n 是树中节点的数量。每个节点被访问一次。
  • 空间复杂度:O(n),递归调用栈的深度最多为树的高度。

示例运行

示例 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]

总结

通过递归方法,我们可以高效地从前序和中序遍历序列构造二叉树。递归地找到根节点在中序遍历中的位置,从而将中序遍历分为左子树和右子树。希望这篇题解对大家有所帮助,如果有任何问题,欢迎在评论区留言讨论!

关注我,获取更多算法题解和编程技巧!

相关文章:

LeetCode 热题 100 105. 从前序与中序遍历序列构造二叉树

LeetCode 热题 100 | 105. 从前序与中序遍历序列构造二叉树 大家好&#xff0c;今天我们来解决一道经典的二叉树问题——从前序与中序遍历序列构造二叉树。这道题在 LeetCode 上被标记为中等难度&#xff0c;要求根据给定的前序遍历和中序遍历序列&#xff0c;构造并返回二叉树…...

IP地址查询助力业务增长

IP地址查询的技术基石 IP地址分为IPv4和IPv6&#xff0c;目前IPv4仍广泛应用&#xff0c;它由四个0-255的十进制数组成&#xff0c;如192.168.1.1。而IPv6为应对IPv4地址枯竭问题而生&#xff0c;采用128位地址长度&#xff0c;极大扩充了地址空间。IP地址查询主要依赖庞大的I…...

Nginx核心功能及同类产品对比

Nginx 作为一款高性能的 Web 服务器和反向代理工具&#xff0c;凭借其独特的架构设计和丰富的功能&#xff0c;成为互联网基础设施中不可或缺的组件。以下是其核心功能及与同类产品&#xff08;如 HAProxy、LVS&#xff09;的对比优势&#xff1a; 一、Nginx 核心功能 高性能架…...

抽奖系统-奖品-活动

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言获取奖品列表前端页面活动创建需求分析活动创建后端实现1-控制层实现及校验活动活动创建后端实现2-保存信息活动插入活动奖品插入 整合活动信息存入redis测试活…...

【Java】 volatile 和 synchronized 的比较及使用场景

在 Java 的并发编程中&#xff0c;volatile 和 synchronized 是两个常用的关键字&#xff0c;它们分别用于保证多线程环境中的 可见性 和 原子性&#xff0c;但它们的工作原理和适用场景却有所不同。今天&#xff0c;我们将深入探讨这两个关键字的异同&#xff0c;帮助大家理解…...

javaScript简单版

简介 JavaScript&#xff08;简称:JS)是一门跨平台、面向对象的脚本语言&#xff0c;是用来控制网页行为&#xff0c;实现页面的交互效果。 JavaScript和Java是完全不同的语言&#xff0c;不论是概念还是设计。但是基础语法类似。 组成: ECMAScript:规定了JS基础语法核心知…...

三种常见接口测试工具(Apipost、Apifox、Postman)

三种常见接口测试工具&#xff08;Apipost、Apifox、Postman&#xff09;的用法及优缺点对比总结&#xff1a; &#x1f527; 一、Apipost ✅ 基本用法 支持 RESTful API、GraphQL、WebSocket 等接口调试自动生成接口文档支持环境变量、接口分组、接口测试用例编写可进行前置…...

蓝桥杯13届国B 完全日期

题目描述。 如果一个日期中年月日的各位数字之和是完全平方数&#xff0c;则称为一个完全日期。 例如&#xff1a;2021 年 6 月 5 日的各位数字之和为 20216516&#xff0c;而 16 是一个完全平方数&#xff0c;它是 4 的平方。所以 2021 年 6 月 5 日是一个完全日期。 例如&…...

kafka connect 大概了解

kafka connect Introduction Kafka Connect is the component of Kafka that provides data integration between databases, key-value stores, search indexes, file systems, and Kafka brokers. kafka connect 是一个框架&#xff0c;用来帮助集成其他系统的数据到kafka…...

嵌入式培训之数据结构学习(三)gdb调试、单向链表练习、顺序表与链表对比

目录 一、gdb调试 &#xff08;一&#xff09;一般调试步骤与命令 &#xff08;二&#xff09;找段错误&#xff08;无下断点的地方&#xff09; &#xff08;三&#xff09;调试命令 二、单向链表练习 1、查找链表的中间结点&#xff08;用快慢指针&#xff09; 2、找出…...

MySQL——九、锁

分类 全局锁表级锁行级锁 全局锁 做全库的逻辑备份 flush tables with read lock; unlock tables;在InnoDB引擎中&#xff0c;我们可以在备份时加上参数–single-transaction参数来完成不加锁的一致性数据备份 mysqldump --single-transaction -uroot -p123456 itcast>…...

精益数据分析(57/126):创业移情阶段的核心要点与实践方法

精益数据分析&#xff08;57/126&#xff09;&#xff1a;创业移情阶段的核心要点与实践方法 在创业的浩瀚征程中&#xff0c;每一个阶段都承载着独特的使命与挑战。今天&#xff0c;我们继续秉持共同进步的理念&#xff0c;深入研读《精益数据分析》&#xff0c;聚焦创业的首…...

服务器被打了怎么应对

云服务器遭受攻击该如何应对&#xff1f; 在互联网时代&#xff0c;不少使用云服务器的网络工作者常常会面临网络攻击的威胁。若云服务器未配置完善的防火墙&#xff0c;极易引发服务器宕机&#xff0c;甚至被封禁隔离&#xff08;俗称“陷入黑洞”&#xff09;&#xff0c;进…...

Halcon案例(二):C#联合Halcon回形针以及方向

本案例分3部分 识别效果,分别显示识别前后识别后;代码展示,分别是Halcon源码和Halcon转为C#的代码代码解释(解释在源码中); 原图如下 识别后图像: 其中计算回形针与X轴之间的夹角 Halcon代码: * clip.hdev: Orientation of clips *识别图像中的回形针,并且计算回形针与X轴之间…...

Spyglass:跨时钟域同步(同步单元)

相关阅读 Spyglasshttps://blog.csdn.net/weixin_45791458/category_12828934.html?spm1001.2014.3001.5482 简介 同步单元方案可以用于控制/数据信号跨时钟域同步&#xff0c;该方案使用约束或参数将目标时钟域中单元指定为同步单元&#xff0c;如图1所示。 图1 同步单元方案…...

JAVA异常体系

在 Java 里&#xff0c;异常体系是其错误处理机制的核心内容&#xff0c;它能够帮助开发者有效应对程序运行时出现的各种意外状况。 异常体系的基本架构 它主要包含两个重要分支&#xff1a; Error&#xff08;错误&#xff09;&#xff1a;这类异常是程序自身无法处理的严重…...

Milvus 视角看主流嵌入式模型(Embeddings)

嵌入是一种机器学习概念&#xff0c;用于将数据映射到高维空间&#xff0c;其中语义相似的数据被紧密排列在一起。嵌入模型通常是 BERT 或其他 Transformer 系列的深度神经网络&#xff0c;它能够有效地用一系列数字&#xff08;称为向量&#xff09;来表示文本、图像和其他数据…...

全面解析 Server-Sent Events(SSE)协议:从大模型流式输出到实时通信场景

全面解析 Server-Sent Events&#xff08;SSE&#xff09;协议&#xff1a;从大模型流式输出到实时通信场景 一、SSE 协议概述 Server-Sent Events&#xff08;SSE&#xff09; 是 HTML5 标准中定义的一种基于 HTTP 的服务器向客户端单向推送实时数据的协议。其核心特性包括&a…...

数据库系统概论|第七章:数据库设计—课程笔记

前言 本章讨论数据库设计的技术和方法&#xff0c;主要讨论基于关系数据库管理系统的关系数据库设计问题&#xff0c;而关于数据库的设计过程中&#xff0c;关于数据模型、关系模型等基本概念在前文中已经有详尽介绍&#xff0c;此处便不再赘述&#xff0c;本文主要围绕概念结…...

Java项目拷打(外卖+点评)

一、点评星球&#xff08;黑马点评&#xff09; 1、项目概述 1.1、项目简介 本项目是基于Spring Boot与Redis深度整合的前后端分离的点评平台。系统以Redis为核心技术支撑&#xff0c;重点解决高并发场景下的缓存穿透、击穿、雪崩等问题&#xff0c;涵盖商户展示、优惠券秒杀…...

MCP:开启AI的“万物互联”时代

MCP&#xff1a;开启AI的“万物互联”时代 ——从协议标准到生态革命的技术跃迁 引言&#xff1a;AI的“最后一公里”困境 在2025年的AI技术浪潮中&#xff0c;大模型已从参数竞赛转向应用落地之争。尽管模型能生成流畅的对话、创作诗歌甚至编写代码&#xff0c;但用户逐渐发现…...

【PostgreSQL数据分析实战:从数据清洗到可视化全流程】附录-D. 扩展插件列表(PostGIS/PostgREST等)

&#x1f449; 点击关注不迷路 &#x1f449; 点击关注不迷路 &#x1f449; 点击关注不迷路 文章大纲 附录D. PostgreSQL扩展插件速查表一、插件分类速查表二、核心插件详解三、安装与配置指南四、应用场景模板五、版本兼容性说明六、维护与优化建议七、官方资源与工具八、附录…...

Spring Boot拦截器详解:原理、实现与应用场景

精心整理了最新的面试资料和简历模板&#xff0c;有需要的可以自行获取 点击前往百度网盘获取 点击前往夸克网盘获取 一、拦截器概述 拦截器&#xff08;Interceptor&#xff09;是Spring MVC框架中用于对请求进行预处理和后处理的组件&#xff0c;主要作用于Controller层。相…...

万字解析:Java字符串

目录 一、 String类 1. String类的初始化 1.1 常用的三种构造String类的方式 1.2 String类如何存储字符串&#xff1f; 2. String类的常用功能方法 2.0 字符串长度的获取 2.1 String对象的比较 2.2 字符/字符串的查找 2.3 字符串的转化 2.4 字符 / 字符串的替换 2.5…...

0514得物、0509滴滴面试总结复盘

目前最欠缺的还是&#xff0c;编码不是很熟&#xff0c;很多都遇到过但是就是写不出来&#xff0c;或者靠背先写一点&#xff0c;然后去加&#xff0c;加的过程没考虑逻辑是不是对的&#xff0c;用滴滴面试官的一句话&#xff0c;就是多刷多练多编码&#xff01; 第二块就是项目…...

记录算法笔记(20025.5.14)对称二叉树

给你一个二叉树的根节点 root &#xff0c; 检查它是否轴对称。 示例 1&#xff1a; 输入&#xff1a;root [1,2,2,3,4,4,3] 输出&#xff1a;true 示例 2&#xff1a; 输入&#xff1a;root [1,2,2,null,3,null,3] 输出&#xff1a;false 提示&#xff1a; 树中节点数目…...

AI大模型从0到1记录学习 linux day23

第 1 章 MySQL概述 1.1 基本概念 1.1.1 数据库是什么&#xff1f; 数据库&#xff08;DB&#xff1a;Database&#xff09;&#xff1a;存储数据的地方。 1.1.2 为什么要用数据库&#xff1f; 应用程序产生的数据是在内存中的&#xff0c;如果程序退出或者是断电了&#xff0c;…...

用git下载vcpkg时出现Connection was reset时的处理

用git安装vcpkg时出现Connect was rest&#xff08;如上图&#xff09;。多谢这位网友的博文解决了问题&#xff1a; 通过:http.sslVerify false全局来设置&#xff0c;执行以下命令&#xff1a; git config --global http.sslVerify "false" 原文链接&#xff1a…...

【数据库复习】SQL语言

一、SQL通用语法与分类 &#xff08;一&#xff09;SQL通用语法 SQL语句的格式通常较为规范&#xff0c;以关键字开头&#xff0c;如CREATE、SELECT、INSERT等&#xff0c;后跟具体的表名、字段名和条件等。在MySQL中&#xff0c;还可以使用help命令获取帮助信息&#xff0c;…...

二叉树——层序遍历

目录 实现层序遍历 判断是否为完全二叉树 实现层序遍历 除了先序遍历&#xff0c;中序遍历&#xff0c;后序遍历外&#xff0c;还可以对二叉树进行层序遍历。设二叉树的结点所在层数为1&#xff0c;层序遍历就是从所在二叉树的根结点出发&#xff0c;首先访问第一层的树根结点…...

Seata源码—2.seata-samples项目介绍

大纲 1.seata-samples的配置文件和启动类 2.seata-samples业务服务启动时的核心工作 3.seata-samples库存服务的连接池配置 4.Seata对数据库连接池代理配置的分析 5.Dubbo RPC通信过程中传递全局事务XID 6.Seata跟Dubbo整合的Filter(基于SPI机制) 7.seata-samples的AT事…...

企业数字化转型背景下的企业知识管理挑战与经验杂谈

一、引言 在数字化转型的浪潮下&#xff0c;企业知识管理正面临前所未有的挑战。随着数据量的急剧增长&#xff0c;企业内部积累的信息呈现出碎片化、分散化的趋势&#xff0c;传统的知识管理体系已难以有效应对这一变革。首先&#xff0c;信息碎片化问题日益严重&#xff0c;…...

第二章:磁盘管理与文件管理

一、磁盘管理 1.windows和Linux磁盘管理的区别 windows资源管理方式 系统一般安装在C盘 C盘下的"Windows"目录是操作系统的核心 C盘下的"Program Files"目录下安装软件 C盘下的"用户"目录是所有的用户&#xff0c;包括超级管理员也在其中 …...

Java版OA管理系统源码 手机版OA系统源码

Java版OA管理系统源码 手机版OA系统源码 一&#xff1a;OA系统的主要优势 1. 提升效率 减少纸质流程和重复性工作&#xff0c;自动化处理常规事务&#xff0c;缩短响应时间。 2. 降低成本 节省纸张、打印、通讯及人力成本&#xff0c;优化资源分配。 3. 规范管理 固化企…...

springboot踩坑记录

之前运行好端端的项目&#xff0c;今天下午打开只是添加了一个文件之后 再运行都报Failed to configure a DataSource: url attribute is not specified and no embedded datasource could be configured.Reason: Failed to determine a suitable driver class Action: Conside…...

SpringAI

机器学习&#xff1a; 定义&#xff1a;人工智能的子领域&#xff0c;通过数据驱动的方法让计算机学习规律&#xff0c;进行预测或决策。 核心方法&#xff1a; 监督学习&#xff08;如线性回归、SVM&#xff09;。 无监督学习&#xff08;如聚类、降维&#xff09;。 强化学…...

acwing 1488. 最短距离 超级源点 最短路 堆优化Dijkstra

经验总结 邻接表 节点1连接到节点2&#xff0c;权重为3。 节点1连接到节点3&#xff0c;权重为5。 节点2连接到节点4&#xff0c;权重为2。 g[1] {{2, 3}, {3, 5}} g[2] {{1, 3}, {4, 2}} g[3] {{1, 5}} g[4] {{2, 2}} vector<vector<PII>> g;题目背景 有 N…...

2002-2024年地级市新质生产力词频统计数据(46个关键词词频)

2002-2024年地级市新质生产力词频统计数据&#xff08;46个关键词词频&#xff09; 1、时间&#xff1a;2002-2024年 2、来源&#xff1a;ZF工作报告 3、指标&#xff1a;行政区划代码、年份、地区、所属省份、文本总长度、仅中英文-文本总长度、文本总词频-全模式、文本总词…...

院校机试刷题第二天:1479 01字符串、1701非素数个数

一、1479 01字符串 1.题目描述 2.解题思路 方法一&#xff1a;暴力法 模拟过程&#xff0c;列出几个数据来a[1]1, a[2]2, a[3]3, a[4]5以此类推&#xff0c;这就是斐波那契数列&#xff0c;每一项都等于前两项之和&#xff0c;确定好a[1], a[2]即可。 方法二&#xff1a;动…...

2011-2019年各省总抚养比数据

2011-2019年各省总抚养比数据 1、时间&#xff1a;2011-2019年 2、来源&#xff1a;国家统计局 3、指标&#xff1a;行政区划代码、地区、年份、总抚养比(人口抽样调查)(%) 4、范围&#xff1a;31省 5、指标解释&#xff1a;总抚养比也称总负担系数。指人口总体中非劳动年…...

3337|3335. 字符串转换后的长度 I(||)

1.字符串转换后的长度 I 1.1题目 3335. 字符串转换后的长度 I - 力扣&#xff08;LeetCode&#xff09; 1.2解析 递推法解析 思路框架 我们可以通过定义状态变量来追踪每次转换后各字符的数量变化。具体地&#xff0c;定义状态函数 f(i,c) 表示经过 i 次转换后&#xff0…...

【电路笔记 通信】8B/10B编码 高速数据传输的串行数据编码技术 论文第三部分 The 8B/10B coding map

0810逻辑总览 The 8B/10B coding map 图 1 展示了一个通信适配器接口&#xff0c;它由八条数据线 A、B、C、D、E、F、G、H&#xff08;注意&#xff1a;使用大写字母表示&#xff09;、一条控制线 K&#xff0c;以及一条以字节速率运行的时钟线 BYTECLK 组成。控制线 K 用于指…...

智能化双语LaTeX系统,分阶段系统性开发技术实现路径:目标是实现语义级编译和认知增强写作,推动跨文明知识表达

智能化双语LaTeX系统&#xff0c;分阶段系统性开发技术实现路径&#xff08;D认为W可辅助各环节开发&#xff09;&#xff1a; 第一阶段&#xff1a;双语LaTeX引擎升级 1. 核心架构设计 Unicode深度支持 开发新一代XeLaTeX/LuaLaTeX内核 原生支持UTF-8编码&#xff08;如汉…...

【RabbitMQ】路由模式和通配符模式的具体实现

文章目录 路由模式创建队列和交换机生产者代码创建交换机声明队列绑定交换机和队列发送消息完整代码 消费者代码运行程序启动生产者启动消费者 通配符模式创建队列和交换机生产者代码创建交换机声明队列绑定交换机和队列发送消息完整代码 消费者代码运行程序启动生产者启动消费…...

【测试开发知识储备】之Jacoco(Java Code Coverage)

文章目录 Jacoco是什么Jacoco的主要功能&#xff08;一&#xff09;多样化覆盖率指标分析&#xff08;二&#xff09; 丰富的报告生成&#xff08;三&#xff09;实时数据收集 Jacoco的工作原理&#xff08;一&#xff09;字节码增强&#xff08;二&#xff09;测试执行与数据收…...

大二java第一面小厂(挂)

第一场&#xff1a; mybatis怎么防止数据转义。 Hutool用的那些你常用的方法。 springboot的常用注解。 redis的多级缓存。 websocket怎么实现的多人协作编辑功能。 怎么实现的分库分表。 mysql里面的各种操作&#xff0c;比如说分表怎么分&#xff0c;分页查询怎么用。 mybat…...

Postman接口测试

现在企业级测试分为三层测试 UI层&#xff1a;即与用户交互的层面 Service层&#xff1a;比如前后端分离的系统&#xff0c;测试数据的传输 Unit层&#xff1a;单元测试 接口 接口的概念很抽象&#xff0c;比如我们经常使用的USB接口&#xff0c;Lighting接口等传输电量数据…...

试除法判断素数优化【C语言】

代码引用 int is_prime(int num) {if (num < 1) return 0;if (num 2 || num 3) return 1;if (num % 2 0 || num % 3 0) return 0;for (int i 5; i * i < num; i 6) {if (num % i 0 || num % (i 2) 0) return 0;}return 1; } 一、数学原理 所有大于3的素数都可…...

全新开发-iVX图形化编程VS完整IDE

本文针对传统软件开发的效率与可控性矛盾&#xff0c;系统阐释 iVX"图形化编程 全栈 IDE" 的复合架构如何突破行业瓶颈。通过 "可视化建模 - 标准代码生成 - 独立运行" 的技术闭环&#xff0c;iVX 实现开发效率提升 60% 与源码完全可控的双重目标。研究揭…...

前端表格滑动滚动条太费事,做个浮动滑动插件

比如下面的表格&#xff0c;因为滚动条样式设计得很窄&#xff0c;所以用鼠标滑动起来很费劲 <template><el-table:data"tableData"style"width: 600px"height"250"><el-table-columnfixedprop"date"label"日期&…...