32 从前序与中序遍历序列构造二叉树
32 从前序与中序遍历序列构造二叉树

32.1 从前序与中序遍历序列构造二叉树解决方案
class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return buildTreeHelper(preorder, inorder, 0, 0, inorder.size() - 1);}TreeNode* buildTreeHelper(vector<int>& preorder, vector<int>& inorder, int& preIdx, int inStart, int inEnd) {// 基本情况:如果遍历到空区间,返回空if (inStart > inEnd) {return nullptr;}// 当前根节点int rootVal = preorder[preIdx++];TreeNode* root = new TreeNode(rootVal);// 在中序遍历中找到根节点位置int rootIdxInInorder = find(inorder.begin() + inStart, inorder.begin() + inEnd, rootVal) - inorder.begin();// 构建左子树root->left = buildTreeHelper(preorder, inorder, preIdx, inStart, rootIdxInInorder - 1);// 构建右子树root->right = buildTreeHelper(preorder, inorder, preIdx, rootIdxInInorder + 1, inEnd);return root;}
};
思路解析:
前序遍历:首先访问根节点,然后访问左子树,再访问右子树。
中序遍历:首先访问左子树,然后访问根节点,最后访问右子树。
步骤:
- 根节点的确定:
- 在前序遍历中,第一个元素就是树的根节点。根据这一点,我们可以直接确定根节点。
- 分割左右子树:
- 在中序遍历中,根节点将数组分成两个部分:左子树和右子树。根节点左边的元素构成左子树,右边的元素构成右子树。
- 递归构建:
- 根据中序遍历分割出的左右子树,递归地在前序和中序遍历中找出对应的子树,继续构建左右子树。
详细步骤
- 获取根节点:从前序遍历的第一个元素得到当前子树的根节点。
- 在中序遍历中查找根节点的位置:根节点左边的元素属于左子树,右边的元素属于右子树。
- 递归构建左右子树:递归地使用剩下的前序和中序遍历来构建左右子树。
代码解析:
- buildTree函数:主要入口函数,调用buildTreeHelper来递归构建二叉树。
- buildTreeHelper函数:递归函数,负责构建树的每个节点。
- preIdx:指示前序遍历中当前根节点的位置。
- inStart和inEnd:指定当前中序遍历子树的范围。
- 每次递归通过preIdx获取根节点的值,通过在中序遍历中找到节点的位置,将数组分为左右子树,递归地构建左右子树。
- find函数:在中序遍历的子数组中找到根节点的位置,用于分割左子树和右子树。
时间复杂度:
- 由于递归遍历每个节点一次,每个节点的查找操作(在find中)在最坏的情况下是 O ( n ) O(n) O(n).
- 总体时间复杂度 O ( n 2 ) O(n^2) O(n2),这是最坏的情况。为了优化,可以使用哈希表记录中序遍历中每个元素的位置,将查找操作优化为 O ( 1 ) O(1) O(1),从而将时间复杂度降低到 O ( n ) O(n) O(n).
32.2 举例说明
举例说明:
假设前序遍历和中序遍历如下:
-
前序遍历:[3,9,20,15,7]
-
中序遍历:[9,3,15,20,7]
-
确定根节点
- 前序遍历的第一个元素是3,所以根节点是3.
-
在中序遍历中找到根节点的位置
- 根节点3在中序遍历中的位置是第2个元素,位置索引为1.
- 这将中序遍历分为:
- 左子树:[9]
- 右子树:[15,20,7]
-
递归构建左子树和右子树
- 对于左子树:
- 在前序遍历中,根节点是9
- 中序遍历中的9就是左子树。左子树为空,右子树也是为空。
- 对于右子树:
- 在前序遍历中,右子树的节点顺序是[20,15,7]
- 在中序遍历中,右子树是[15,20,7]。
- 对于左子树:
相关文章:
32 从前序与中序遍历序列构造二叉树
32 从前序与中序遍历序列构造二叉树 32.1 从前序与中序遍历序列构造二叉树解决方案 class Solution { public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {return buildTreeHelper(preorder, inorder, 0, 0, inorder.size() - 1)…...
D82【python 接口自动化学习】- pytest基础用法
day82 pytest初体验 学习日期:20241128 学习目标:pytest基础用法 -- pytest初体验 学习笔记: 文件命名规范 py测试文件必须以test_开头(或_test结尾)测试方法必须以test开头测试类必须以Test开头,并且…...
在开发环境中,前端(手机端),后端(电脑端),那么应该如何设置iisExpress
首先,要想手机端应用能成功请求后端,两个设备至少需在同一个局域网内,且IP地址互通; 因为ajax是http(s)://IP地址端口号的方式请求,但是iisExpress默认是localhost如何解决,并没有IP地址,所以手…...
磁盘/系统空间占满导致黑屏死机无法开机的解决办法
文章目录 起因具体操作1.重启虚拟机,一直按CtrlShitf进入GRUP界面2.选“Ubuntu高级选项”并回车选择第二个,recovery mode3.4.命令查看磁盘情况5.查找和删除文…...
使用zabbix监控k8s
一、 参考文献 小阿轩yx-案例:Zabbix监控kubernetes云原生环境 手把手教你实现zabbix对Kubernetes的监控 二、部署经验 关于zabbix监控k8s,总体来说是分为两块内容,一是在k8s集群部署zabbix-agent和zabbix- proxy。二是在zabbix进行配置。…...
MacOS安装MySQL数据库和Java环境以及Navicat
安装MySQL 去官网下载:MySQL 下载好后安装,在设置里往下滑,出现了这样,就代表安装成功了 接下来配置环境: 首先在我们的设备上找到终端并打开,输入 vim ~/.bash_profile(注意vim后面的空格),输入完成后点击…...
算法的复杂度
1.数据结构前言 下面的概念有的比较难理解,做个了结就行。 1.1数据结构的起源 在现实生活中我们更多地并不是解决数值计算的问题,而是 需要一些更科学的手段如(表,数,图等数据结构),才能更好…...
Linux命令进阶·如何切换root以及回退、sudo命令、用户/用户组管理,以及解决创建用户不显示问题和Ubuntu不显示用户名只显示“$“符号问题
目录 1. root用户(超级管理员) 1.1 用于账户切换的系统命令——su 1.2 退回上一个用户命令——exit 1.3 普通命令临时授权root身份执行——sudo 1.3.1 为普通用户配置sudo认证 2. 用户/用户组管理 2.1 用户组管理 2.2 用户管理 2.2.1 …...
若依项目源码阅读
源码阅读 前端代码分析 代码生成器生成的前端代码有两个,分别是course.js用于向后端发送ajax请求的接口代码,另一个是index.vue,用于在浏览器展示课程管理的视图组件。前端的代码是基于vue3elementplus。 template用于展示前端组件别的标签…...
JVM知识点学习-1
学习视频:狂神说Java 类加载器和双亲委派机制 类加载器 作用:加载Class文件 流程:这里的名字car1。。在栈里面,但是数据在堆里面 类加载器的几个类型: 虚拟机自带的类加载器;启动类(根Boot…...
TypeScript和JavaScript区别详解
文章目录 TypeScript和JavaScript区别详解一、引言二、类型系统1、静态类型检查TypeScript 示例JavaScript 示例 2、类型推断TypeScript 示例JavaScript 示例 三、面向对象编程TypeScript 示例JavaScript 示例 四、使用示例1. 环境搭建2. 创建TypeScript项目3. 安装TypeScript插…...
RVO动态避障技术方案介绍
原文:RVO动态避障技术方案介绍 - 哔哩哔哩 我们在开发游戏的时候经常会遇到这样的问题,当我们寻路的时候,其它人也在寻路,如何避免不从其它人的位置穿过。这个叫做动态避障,目前主流的解决方案就是RVO。本节我们来介绍…...
Vue进阶之单组件开发与组件通信
书接上篇,我们了解了如何快速创建一个脚手架,现在我们来学习如何基于vite创建属于自己的脚手架。在创建一个新的组件时,要在新建文件夹中打开终端创建一个基本的脚手架,可在脚手架中原有的文件中修改或在相应路径重新创建…...
OGRE 3D----5. OGRE和QML事件交互
在现代图形应用程序开发中,OGRE(Object-Oriented Graphics Rendering Engine)作为一个高性能的3D渲染引擎,广泛应用于游戏开发、虚拟现实和仿真等领域。而QML(Qt Modeling Language)则是Qt框架中的一种声明式语言,专注于设计用户界面。将OGRE与QML结合,可以充分利用OGR…...
ARIMA-神经网络混合模型在时间序列预测中的应用
ARIMA-神经网络混合模型在时间序列预测中的应用 1. 引言 1.1 研究背景与意义 时间序列预测在现代数据科学中扮演着越来越重要的角色。从金融市场的价格走势到工业生产的需求预测,从气象数据的天气预报到用电量的负荷预测,时间序列分析无处不在。传统的统计方法和现代深度学习…...
常见靶场的搭建
漏洞靶场 渗透测试(漏洞挖掘)切忌纸上谈兵,学习渗透测试(漏洞挖掘)知识的过程中,我们通常需要一个包含漏洞的测试环境来进行训练。而在非授权情况下,对于网站进行渗透测试攻击,是触及…...
[MacOS] [kubernetes] MacOS玩转虚拟化最佳实践
❓ 为什么不在MacOS本机安装呢?因为M系列芯片是Arm架构,与生产环境或者在本地调试时候,安装虚拟镜像和X86不同,造成不必要的切换环境的额外成本,所以在虚拟化的x86调试 步骤 & 详情 一: 安装OrbStack & 并配置…...
HarmonyOS:@Provide装饰器和@Consume装饰器:与后代组件双向同步
一、前言 Provide和Consume,应用于与后代组件的双向数据同步,应用于状态数据在多个层级之间传递的场景。不同于上文提到的父子组件之间通过命名参数机制传递,Provide和Consume摆脱参数传递机制的束缚,实现跨层级传递。 其中Provi…...
git 上传代码时报错
在上传代码时,显示无法上传 PS E:\JavaWeb\vue3-project> git push To https://gitee.com/evening-breeze-2003/vue3.git! [rejected] master -> master (non-fast-forward) error: failed to push some refs to https://gitee.com/evening-breeze-20…...
判断1456789876541是否为素数,是输出“是素数“,不是则输出“不是素数“
题目描述 判断1456789876541是否为素数,是输出"是素数",不是则输出"不是素数" 代码实现 int main() { long long n 1456789876541; //for (long long i 2; i < n; i)//数据量太大 for(long long i2;i<sqrt(n);i)//素数的优化 { if (n % i 0) …...
华为云AI开发平台ModelArts
华为云ModelArts:重塑AI开发流程的“智能引擎”与“创新加速器”! 在人工智能浪潮席卷全球的2025年,企业拥抱AI的意愿空前高涨,但技术门槛高、流程复杂、资源投入巨大的现实,却让许多创新构想止步于实验室。数据科学家…...
HTML 语义化
目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案: 语义化标签: <header>:页头<nav>:导航<main>:主要内容<article>&#x…...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来,Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
mongodb源码分析session执行handleRequest命令find过程
mongo/transport/service_state_machine.cpp已经分析startSession创建ASIOSession过程,并且验证connection是否超过限制ASIOSession和connection是循环接受客户端命令,把数据流转换成Message,状态转变流程是:State::Created 》 St…...
1688商品列表API与其他数据源的对接思路
将1688商品列表API与其他数据源对接时,需结合业务场景设计数据流转链路,重点关注数据格式兼容性、接口调用频率控制及数据一致性维护。以下是具体对接思路及关键技术点: 一、核心对接场景与目标 商品数据同步 场景:将1688商品信息…...
JVM垃圾回收机制全解析
Java虚拟机(JVM)中的垃圾收集器(Garbage Collector,简称GC)是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象,从而释放内存空间,避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
springboot整合VUE之在线教育管理系统简介
可以学习到的技能 学会常用技术栈的使用 独立开发项目 学会前端的开发流程 学会后端的开发流程 学会数据库的设计 学会前后端接口调用方式 学会多模块之间的关联 学会数据的处理 适用人群 在校学生,小白用户,想学习知识的 有点基础,想要通过项…...
