LeetCode 热题 100_从前序与中序遍历序列构造二叉树(47_105_中等_C++)(二叉树;递归)
LeetCode 热题 100_从前序与中序遍历序列构造二叉树(47_105)
- 题目描述:
- 输入输出样例:
- 题解:
- 解题思路:
- 思路一(递归):
- 代码实现
- 代码实现(思路一(递归)):
- 以思路一为例进行调试
题目描述:
给定两个整数数组 preorder 和 inorder ,其中 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
preorder 和 inorder 均 无重复 元素
inorder 均出现在 preorder
preorder 保证 为二叉树的前序遍历序列
inorder 保证 为二叉树的中序遍历序列
题解:
解题思路:
思路一(递归):
1、分析中序遍历和先序遍历的特点:
先序遍历:根 左 右
中序遍历: 左 根 右
① 我们可以通过先序遍历第一个结点来确定当前的根节点。
② 通过preorder和inorder均无重复元素,则可通过当前的根节点唯一确定中序遍历中当前根节点的位置,从而将中序遍历序列划分为左 根 右三个区间。
③ 通过中序遍历划分的左 根 右三个区间,就可以将先序序列的左右区间也划分出来。
④ 将划分的左右区间分别进行上述过程直至左右区间没有元素为止。
⑤ 我们发现上述是一个递归的过程。
⑥ 通过先序遍历第一个元素查找其在中序遍历中的位置是很耗费时间的,我们可以建立一个哈希表来存储中序遍历元素值和下标的对应关系,这样便能节省查找的时间。
2、复杂度分析:
① 时间复杂度:O(n),n代表前序遍历或中序遍历中元素的个数。将中序遍历中的n个数据存入哈希表时间为O(n),将n个元素转换为二叉树O(n)。
② 空间复杂度:O(n),n代表前序遍历或中序遍历中元素的个数。将中序遍历中的n个数据存入哈希表所需空间为O(n),递归创建二叉树最坏的情况下为O(n)。
代码实现
代码实现(思路一(递归)):
class Solution {
private:unordered_map<int,int> inorderVal_index;public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {//计算先序遍历数组和中序遍历数组的大小,其实这两个是一样的int preLen = preorder.size();int inLen = inorder.size();//将中序遍历的元素和下标的对应关系存储到哈希表中for (int i = 0; i < inLen; i++){inorderVal_index[inorder[i]]=i;}//递归的构建二叉树,包含先序和中序数组,和其对应的范围下标return myBuildTree(preorder,inorder,0,preLen-1,0,inLen-1);}TreeNode* myBuildTree(vector<int>& preorder, vector<int>& inorder,int preorder_left,int preorder_right,int inorder_left,int inorder_right ){//如果区间元素为0则返回nullptr,也就是叶节点链接的nullptrif (preorder_left>preorder_right){return nullptr;}//inorder_root代表中序遍历序列中根节点的下标int inorder_root=inorderVal_index[preorder[preorder_left]];//先序遍历第一个结点就是根节点,创建根节点TreeNode *root=new TreeNode(preorder[preorder_left]);//通过根在中序遍历的位置确定左区间的大小,从而推出先序遍历的左右区间int size_left_subtree=inorder_root-inorder_left;//在左子区间递归的进行上述过程root->left=myBuildTree(preorder,inorder,preorder_left+1,preorder_left+size_left_subtree,inorder_left,inorder_root-1);//在右子区间递归的进行上述过程root->right=myBuildTree(preorder,inorder,preorder_left+size_left_subtree+1,preorder_right,inorder_root+1,inorder_right);return root;}};
以思路一为例进行调试
#include<iostream>
#include <vector>
#include <unordered_map>
using namespace std;struct TreeNode {int val;TreeNode *left;TreeNode *right;TreeNode() : val(0), left(nullptr), right(nullptr) {}TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};//中序遍历输出节点的值
void inorder_print(TreeNode *root){if (root==nullptr) return ;inorder_print(root->left);if(root!=nullptr){cout<<root->val<<" ";}else{cout<<"null ";}inorder_print(root->right);
}//方法一:
class Solution {
private:unordered_map<int,int> inorderVal_index;public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {//计算先序遍历数组和中序遍历数组的大小,其实这两个是一样的int preLen = preorder.size();int inLen = inorder.size();//将中序遍历的元素和下标的对应关系存储到哈希表中for (int i = 0; i < inLen; i++){inorderVal_index[inorder[i]]=i;}//递归的构建二叉树,包含先序和中序数组,和其对应的范围下标return myBuildTree(preorder,inorder,0,preLen-1,0,inLen-1);}TreeNode* myBuildTree(vector<int>& preorder, vector<int>& inorder,int preorder_left,int preorder_right,int inorder_left,int inorder_right ){//如果区间元素为0则返回nullptr,也就是叶节点链接的nullptrif (preorder_left>preorder_right){return nullptr;}//inorder_root代表中序遍历序列中根节点的下标int inorder_root=inorderVal_index[preorder[preorder_left]];//先序遍历第一个结点就是根节点,创建根节点TreeNode *root=new TreeNode(preorder[preorder_left]);//通过根在中序遍历的位置确定左区间的大小,从而推出先序遍历的左右区间int size_left_subtree=inorder_root-inorder_left;//在左子区间递归的进行上述过程root->left=myBuildTree(preorder,inorder,preorder_left+1,preorder_left+size_left_subtree,inorder_left,inorder_root-1);//在右子区间递归的进行上述过程root->right=myBuildTree(preorder,inorder,preorder_left+size_left_subtree+1,preorder_right,inorder_root+1,inorder_right);return root;}};int main(int argc, char const *argv[])
{//前序遍历和中序遍历vector<int> preorder={3,9,20,15,7};vector<int> inorder={9,3,15,20,7};//通过先序遍历和中序遍历构造二叉树Solution s;TreeNode *root= s.buildTree(preorder,inorder);//中序遍历输出构造的二叉树inorder_print(root);return 0;
}
LeetCode 热题 100_从前序与中序遍历序列构造二叉树(47_105)原题链接
欢迎大家和我沟通交流(✿◠‿◠)
相关文章:
LeetCode 热题 100_从前序与中序遍历序列构造二叉树(47_105_中等_C++)(二叉树;递归)
LeetCode 热题 100_从前序与中序遍历序列构造二叉树(47_105) 题目描述:输入输出样例:题解:解题思路:思路一(递归): 代码实现代码实现(思路一(递归…...
使用sqlplus的easy connect时如何指定是链接到shared server还是dedicated process
在oracle配置了shared server的情况下 可以使用 :shared来指定链接到shared server也可以默认不指定 不指定的情况下会默认链接到shared server 如果想链接到 dedicated process 则必须显式指定链接到dedicated process server type的类型包括DEDICATED, SHARED, or POOLED. […...
ubuntu22.4 ROS2 安装gazebo(环境变量配置)
ubuntu版本:ubuntu22.4 最近在学习ROS2 视频教程古月居的入门课: 视频教程 文字笔记 问题 在学到关于Gazebo的时候,遇到下面问题: 运行 $ ros2 launch gazebo_ros gazebo.launch.py在这里卡住,不弹出gazebo 解决…...
【机器学习:十四、TensorFlow与PyTorch的对比分析】
1. 发展背景与社区支持 1.1 TensorFlow的背景与发展 TensorFlow是Google于2015年发布的开源深度学习框架,基于其前身DistBelief系统。作为Google大规模深度学习研究成果的延续,TensorFlow从一开始就定位为生产级框架,强调跨平台部署能力和性…...
[C++]类与对象(上)
目录 💕1.C中结构体的优化 💕2.类的定义 💕3.类与结构体的不同点 💕4.访问限定符(public,private,protected) 💕5.类域 💕6.类的实例化 💕7.类的字节大小 💕8.类的字节大小特例…...
大数据技术实训:Zookeeper集群配置
一、本地模式安装部署 1)安装前准备 (1)安装jdk (2)拷贝Zookeeper安装包到Linux系统下 (3)解压到指定目录 tar -zxvf zookeeper-3.5.7.tar.gz -C /opt/module/ 2)配置修改 &am…...
HTML5 加载动画(Loading Animation)
加载动画(Loading Animation)详解 概述 加载动画是指在数据加载过程中,向用户展示的一种视觉效果,旨在提升用户体验,告知用户系统正在处理请求。它可以减少用户的等待焦虑感,提高界面的互动性。 常见的加…...
C语言进阶-2指针(一)
目录 1. 字符指针1.1 一般用法:字符指针指向单字符1.2 第二种用法,字符串首地址给指针变量1.3 习题,下面代码的输出结果是什么?为什么? 2. 指针数组2.1实例—— 字符指针数组2.2实例——整形指针数组2.3 例子,识别下下…...
【人工智能】用Python进行对象检测:从OpenCV到YOLO的全面指南
对象检测是计算机视觉领域的核心任务之一,广泛应用于视频监控、自动驾驶、智能安防等多个场景。随着深度学习技术的发展,基于传统方法的对象检测逐渐被基于神经网络的先进模型所取代。本文将系统地介绍如何使用Python进行对象检测,重点探讨了…...
《深度剖析算法优化:提升效率与精度的秘诀》
想象一下,你面前有一堆杂乱无章的数据,你需要从中找到特定的信息,或者按照一定的规则对这些数据进行排序。又或者,你要为一个物流公司规划最佳的配送路线,以降低成本和提高效率。这些问题看似复杂,但都可以…...
Mysql--重点篇--索引(索引分类,Hash和B-tree索引,聚簇和非聚簇索引,回表查询,覆盖索引,索引工作原理,索引失效,索引创建原则等)
索引是数据库中用于加速查询操作的重要机制。通过索引,MySQL可以快速定位到满足查询条件的数据行,而不需要扫描整个表。合理的索引设计可以显著提高查询性能,但不合理的索引可能会导致性能下降和磁盘空间浪费。因此,理解索引的工作…...
matlab使用 BP 神经网络进行数据预测的完整流程,包括数据读取、数据预处理等等
%% 初始化程序 warning off % 关闭报警信息 close all % 关闭所有图窗 clear % 清空变量 clc % 清空命令行 setdemorandstream(172) %设置随机种子为1%% 读取数据 data xlsread(Y.xlsx); %% 划分训练集…...
systemd-networkd NetworkManager 介绍
systemd-networkd 和 NetworkManager 的详细介绍 systemd-networkd 和 NetworkManager 都是 Linux 系统中常用的网络管理工具,但它们的设计目标和使用场景不同。以下是它们的详细介绍、功能、使用场景和差异。 1. systemd-networkd systemd-networkd 是一个由 syst…...
本地部署项目管理工具 Leantime 并实现外部访问
Leantime 是一款开源 AI 项目。它可以在本地直接运行大语言模型 LLM、生成图像、音频等。直接降低了用户使用AI的门褴。本文将详细的介绍如何利用 Docker 在本地部署 Leantime 并结合路由侠实现外网访问本地部署的 Leantime 。 第一步,本地部署安装 Leantime 1&am…...
PHP cURL 函数初学者完全指南
文章精选推荐 1 JetBrains Ai assistant 编程工具让你的工作效率翻倍 2 Extra Icons:JetBrains IDE的图标增强神器 3 IDEA插件推荐-SequenceDiagram,自动生成时序图 4 BashSupport Pro 这个ides插件主要是用来干嘛的 ? 5 IDEA必装的插件&…...
C#中的Array数组,List集合和ArrayList集合--07
目录 一.Array数组概念的简单理解 1.数组的初始化 2.数组的长度 3.数组的克隆和复制 4.数组的清空 5.数组的查找 6.数组的逆转 7.数组的拓展和缩减 8.数组的比较 9.数组的合并 10.使用Array类中的静态方法,如Array.Sort,Array.BinarySearch 等 二.Array数组进阶 1.二…...
基于深度学习的视觉检测小项目(十三) 资源文件的生成和调用
在使用 PySide6 进行开发时,管理应用程序的资源(如图标、图片、字体、样式表、音视频等)是一个常见的任务。PySide6 提供了一个工具 pyside6-rcc,它能够将资源文件(.qrc)编译成 Python 模块,然后…...
硬件实用技巧:TPS54331DR横杠标识识别1引脚
若该文为原创文章,转载请注明原文出处 本文章博客地址:https://hpzwl.blog.csdn.net/article/details/145116969 长沙红胖子Qt(长沙创微智科)博文大全:开发技术集合(包含Qt实用技术、树莓派、三维、OpenCV…...
《C++11》nullptr介绍:从NULL说起
在C11之前,我们通常使用NULL来表示空指针。然而,NULL在C中有一些问题和限制,这就是C11引入nullptr的原因。本文将详细介绍nullptr的定义、用法和优点。 1. NULL的问题 在C中,NULL实际上是一个整数0,而不是一个真正的…...
自然语言处理基础:全面概述
自然语言处理基础:全面概述 什么是NLP及其重要性、NLP的核心组件、NLU与NLG、NLU与NLG的集成、NLP的挑战以及NLP的未来 自然语言处理(NLP)是人工智能(AI)中最引人入胜且具有影响力的领域之一。它驱动着我们日常使用的…...
逻辑回归:给不确定性划界的分类大师
想象你是一名医生。面对患者的检查报告(肿瘤大小、血液指标),你需要做出一个**决定性判断**:恶性还是良性?这种“非黑即白”的抉择,正是**逻辑回归(Logistic Regression)** 的战场&a…...
Vue3 + Element Plus + TypeScript中el-transfer穿梭框组件使用详解及示例
使用详解 Element Plus 的 el-transfer 组件是一个强大的穿梭框组件,常用于在两个集合之间进行数据转移,如权限分配、数据选择等场景。下面我将详细介绍其用法并提供一个完整示例。 核心特性与用法 基本属性 v-model:绑定右侧列表的值&…...
Module Federation 和 Native Federation 的比较
前言 Module Federation 是 Webpack 5 引入的微前端架构方案,允许不同独立构建的应用在运行时动态共享模块。 Native Federation 是 Angular 官方基于 Module Federation 理念实现的专为 Angular 优化的微前端方案。 概念解析 Module Federation (模块联邦) Modul…...
Rust 异步编程
Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别
OpenPrompt 和直接对提示词的嵌入向量进行训练有什么区别 直接训练提示词嵌入向量的核心区别 您提到的代码: prompt_embedding = initial_embedding.clone().requires_grad_(True) optimizer = torch.optim.Adam([prompt_embedding...
3-11单元格区域边界定位(End属性)学习笔记
返回一个Range 对象,只读。该对象代表包含源区域的区域上端下端左端右端的最后一个单元格。等同于按键 End 向上键(End(xlUp))、End向下键(End(xlDown))、End向左键(End(xlToLeft)End向右键(End(xlToRight)) 注意:它移动的位置必须是相连的有内容的单元格…...
2025季度云服务器排行榜
在全球云服务器市场,各厂商的排名和地位并非一成不变,而是由其独特的优势、战略布局和市场适应性共同决定的。以下是根据2025年市场趋势,对主要云服务器厂商在排行榜中占据重要位置的原因和优势进行深度分析: 一、全球“三巨头”…...
Docker 本地安装 mysql 数据库
Docker: Accelerated Container Application Development 下载对应操作系统版本的 docker ;并安装。 基础操作不再赘述。 打开 macOS 终端,开始 docker 安装mysql之旅 第一步 docker search mysql 》〉docker search mysql NAME DE…...
MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用
文章目录 一、背景知识:什么是 B-Tree 和 BTree? B-Tree(平衡多路查找树) BTree(B-Tree 的变种) 二、结构对比:一张图看懂 三、为什么 MySQL InnoDB 选择 BTree? 1. 范围查询更快 2…...
Qt 事件处理中 return 的深入解析
Qt 事件处理中 return 的深入解析 在 Qt 事件处理中,return 语句的使用是另一个关键概念,它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 核心区别:不同层级的事件处理 方…...
