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) …...

深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例
文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...

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

【开发技术】.Net使用FFmpeg视频特定帧上绘制内容
目录 一、目的 二、解决方案 2.1 什么是FFmpeg 2.2 FFmpeg主要功能 2.3 使用Xabe.FFmpeg调用FFmpeg功能 2.4 使用 FFmpeg 的 drawbox 滤镜来绘制 ROI 三、总结 一、目的 当前市场上有很多目标检测智能识别的相关算法,当前调用一个医疗行业的AI识别算法后返回…...

云原生玩法三问:构建自定义开发环境
云原生玩法三问:构建自定义开发环境 引言 临时运维一个古董项目,无文档,无环境,无交接人,俗称三无。 运行设备的环境老,本地环境版本高,ssh不过去。正好最近对 腾讯出品的云原生 cnb 感兴趣&…...

Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...

【Post-process】【VBA】ETABS VBA FrameObj.GetNameList and write to EXCEL
ETABS API实战:导出框架元素数据到Excel 在结构工程师的日常工作中,经常需要从ETABS模型中提取框架元素信息进行后续分析。手动复制粘贴不仅耗时,还容易出错。今天我们来用简单的VBA代码实现自动化导出。 🎯 我们要实现什么? 一键点击,就能将ETABS中所有框架元素的基…...
Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解
文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一:HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二:Floyd 快慢指针法(…...