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

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初体验 学习日期&#xff1a;20241128 学习目标&#xff1a;pytest基础用法 -- pytest初体验 学习笔记&#xff1a; 文件命名规范 py测试文件必须以test_开头&#xff08;或_test结尾&#xff09;测试方法必须以test开头测试类必须以Test开头&#xff0c;并且…...

在开发环境中,前端(手机端),后端(电脑端),那么应该如何设置iisExpress

首先&#xff0c;要想手机端应用能成功请求后端&#xff0c;两个设备至少需在同一个局域网内&#xff0c;且IP地址互通&#xff1b; 因为ajax是http(s)://IP地址端口号的方式请求&#xff0c;但是iisExpress默认是localhost如何解决&#xff0c;并没有IP地址&#xff0c;所以手…...

磁盘/系统空间占满导致黑屏死机无法开机的解决办法

文章目录 起因具体操作1.重启虚拟机&#xff0c;一直按CtrlShitf进入GRUP界面2.选“Ubuntu高级选项”并回车选择第二个&#xff0c;recovery mode![请添加图片描述](https://i-blog.csdnimg.cn/direct/201f9784c203406d802d24b39dc2d4a3.png)3.4.命令查看磁盘情况5.查找和删除文…...

使用zabbix监控k8s

一、 参考文献 小阿轩yx-案例&#xff1a;Zabbix监控kubernetes云原生环境 手把手教你实现zabbix对Kubernetes的监控 二、部署经验 关于zabbix监控k8s&#xff0c;总体来说是分为两块内容&#xff0c;一是在k8s集群部署zabbix-agent和zabbix- proxy。二是在zabbix进行配置。…...

MacOS安装MySQL数据库和Java环境以及Navicat

安装MySQL 去官网下载&#xff1a;MySQL 下载好后安装&#xff0c;在设置里往下滑&#xff0c;出现了这样&#xff0c;就代表安装成功了 接下来配置环境&#xff1a; 首先在我们的设备上找到终端并打开,输入 vim ~/.bash_profile(注意vim后面的空格)&#xff0c;输入完成后点击…...

算法的复杂度

1.数据结构前言 下面的概念有的比较难理解&#xff0c;做个了结就行。 1.1数据结构的起源 在现实生活中我们更多地并不是解决数值计算的问题&#xff0c;而是 需要一些更科学的手段如&#xff08;表&#xff0c;数&#xff0c;图等数据结构&#xff09;&#xff0c;才能更好…...

Linux命令进阶·如何切换root以及回退、sudo命令、用户/用户组管理,以及解决创建用户不显示问题和Ubuntu不显示用户名只显示“$“符号问题

目录 1. root用户&#xff08;超级管理员&#xff09; 1.1 用于账户切换的系统命令——su 1.2 退回上一个用户命令——exit 1.3 普通命令临时授权root身份执行——sudo 1.3.1 为普通用户配置sudo认证 2. 用户/用户组管理 2.1 用户组管理 2.2 用户管理 2.2.1 …...

若依项目源码阅读

源码阅读 前端代码分析 代码生成器生成的前端代码有两个&#xff0c;分别是course.js用于向后端发送ajax请求的接口代码&#xff0c;另一个是index.vue&#xff0c;用于在浏览器展示课程管理的视图组件。前端的代码是基于vue3elementplus。 template用于展示前端组件别的标签…...

JVM知识点学习-1

学习视频&#xff1a;狂神说Java 类加载器和双亲委派机制 类加载器 作用&#xff1a;加载Class文件 流程&#xff1a;这里的名字car1。。在栈里面&#xff0c;但是数据在堆里面 类加载器的几个类型&#xff1a; 虚拟机自带的类加载器&#xff1b;启动类&#xff08;根Boot…...

TypeScript和JavaScript区别详解

文章目录 TypeScript和JavaScript区别详解一、引言二、类型系统1、静态类型检查TypeScript 示例JavaScript 示例 2、类型推断TypeScript 示例JavaScript 示例 三、面向对象编程TypeScript 示例JavaScript 示例 四、使用示例1. 环境搭建2. 创建TypeScript项目3. 安装TypeScript插…...

RVO动态避障技术方案介绍

原文&#xff1a;RVO动态避障技术方案介绍 - 哔哩哔哩 我们在开发游戏的时候经常会遇到这样的问题&#xff0c;当我们寻路的时候&#xff0c;其它人也在寻路&#xff0c;如何避免不从其它人的位置穿过。这个叫做动态避障&#xff0c;目前主流的解决方案就是RVO。本节我们来介绍…...

Vue进阶之单组件开发与组件通信

书接上篇&#xff0c;我们了解了如何快速创建一个脚手架&#xff0c;现在我们来学习如何基于vite创建属于自己的脚手架。在创建一个新的组件时&#xff0c;要在新建文件夹中打开终端创建一个基本的脚手架&#xff0c;可在脚手架中原有的文件中修改或在相应路径重新创建&#xf…...

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 研究背景与意义 时间序列预测在现代数据科学中扮演着越来越重要的角色。从金融市场的价格走势到工业生产的需求预测,从气象数据的天气预报到用电量的负荷预测,时间序列分析无处不在。传统的统计方法和现代深度学习…...

常见靶场的搭建

漏洞靶场 渗透测试&#xff08;漏洞挖掘&#xff09;切忌纸上谈兵&#xff0c;学习渗透测试&#xff08;漏洞挖掘&#xff09;知识的过程中&#xff0c;我们通常需要一个包含漏洞的测试环境来进行训练。而在非授权情况下&#xff0c;对于网站进行渗透测试攻击&#xff0c;是触及…...

[MacOS] [kubernetes] MacOS玩转虚拟化最佳实践

❓ 为什么不在MacOS本机安装呢&#xff1f;因为M系列芯片是Arm架构&#xff0c;与生产环境或者在本地调试时候&#xff0c;安装虚拟镜像和X86不同&#xff0c;造成不必要的切换环境的额外成本&#xff0c;所以在虚拟化的x86调试 步骤 & 详情 一: 安装OrbStack & 并配置…...

HarmonyOS:@Provide装饰器和@Consume装饰器:与后代组件双向同步

一、前言 Provide和Consume&#xff0c;应用于与后代组件的双向数据同步&#xff0c;应用于状态数据在多个层级之间传递的场景。不同于上文提到的父子组件之间通过命名参数机制传递&#xff0c;Provide和Consume摆脱参数传递机制的束缚&#xff0c;实现跨层级传递。 其中Provi…...

git 上传代码时报错

在上传代码时&#xff0c;显示无法上传 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) …...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

DockerHub与私有镜像仓库在容器化中的应用与管理

哈喽&#xff0c;大家好&#xff0c;我是左手python&#xff01; Docker Hub的应用与管理 Docker Hub的基本概念与使用方法 Docker Hub是Docker官方提供的一个公共镜像仓库&#xff0c;用户可以在其中找到各种操作系统、软件和应用的镜像。开发者可以通过Docker Hub轻松获取所…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

三体问题详解

从物理学角度&#xff0c;三体问题之所以不稳定&#xff0c;是因为三个天体在万有引力作用下相互作用&#xff0c;形成一个非线性耦合系统。我们可以从牛顿经典力学出发&#xff0c;列出具体的运动方程&#xff0c;并说明为何这个系统本质上是混沌的&#xff0c;无法得到一般解…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...

基于鸿蒙(HarmonyOS5)的打车小程序

1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...