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

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_从前序与中序遍历序列构造二叉树&#xff08;47_105&#xff09; 题目描述&#xff1a;输入输出样例&#xff1a;题解&#xff1a;解题思路&#xff1a;思路一&#xff08;递归&#xff09;&#xff1a; 代码实现代码实现&#xff08;思路一&#xff08;递归…...

使用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版本&#xff1a;ubuntu22.4 最近在学习ROS2 视频教程古月居的入门课&#xff1a; 视频教程 文字笔记 问题 在学到关于Gazebo的时候&#xff0c;遇到下面问题&#xff1a; 运行 $ ros2 launch gazebo_ros gazebo.launch.py在这里卡住&#xff0c;不弹出gazebo 解决…...

【机器学习:十四、TensorFlow与PyTorch的对比分析】

1. 发展背景与社区支持 1.1 TensorFlow的背景与发展 TensorFlow是Google于2015年发布的开源深度学习框架&#xff0c;基于其前身DistBelief系统。作为Google大规模深度学习研究成果的延续&#xff0c;TensorFlow从一开始就定位为生产级框架&#xff0c;强调跨平台部署能力和性…...

[C++]类与对象(上)

目录 &#x1f495;1.C中结构体的优化 &#x1f495;2.类的定义 &#x1f495;3.类与结构体的不同点 &#x1f495;4.访问限定符(public,private,protected) &#x1f495;5.类域 &#x1f495;6.类的实例化 &#x1f495;7.类的字节大小 &#x1f495;8.类的字节大小特例…...

大数据技术实训:Zookeeper集群配置

一、本地模式安装部署 1&#xff09;安装前准备 &#xff08;1&#xff09;安装jdk &#xff08;2&#xff09;拷贝Zookeeper安装包到Linux系统下 &#xff08;3&#xff09;解压到指定目录 tar -zxvf zookeeper-3.5.7.tar.gz -C /opt/module/ 2&#xff09;配置修改 &am…...

HTML5 加载动画(Loading Animation)

加载动画&#xff08;Loading Animation&#xff09;详解 概述 加载动画是指在数据加载过程中&#xff0c;向用户展示的一种视觉效果&#xff0c;旨在提升用户体验&#xff0c;告知用户系统正在处理请求。它可以减少用户的等待焦虑感&#xff0c;提高界面的互动性。 常见的加…...

C语言进阶-2指针(一)

目录 1. 字符指针1.1 一般用法&#xff1a;字符指针指向单字符1.2 第二种用法&#xff0c;字符串首地址给指针变量1.3 习题,下面代码的输出结果是什么&#xff1f;为什么&#xff1f; 2. 指针数组2.1实例—— 字符指针数组2.2实例——整形指针数组2.3 例子&#xff0c;识别下下…...

【人工智能】用Python进行对象检测:从OpenCV到YOLO的全面指南

对象检测是计算机视觉领域的核心任务之一&#xff0c;广泛应用于视频监控、自动驾驶、智能安防等多个场景。随着深度学习技术的发展&#xff0c;基于传统方法的对象检测逐渐被基于神经网络的先进模型所取代。本文将系统地介绍如何使用Python进行对象检测&#xff0c;重点探讨了…...

《深度剖析算法优化:提升效率与精度的秘诀》

想象一下&#xff0c;你面前有一堆杂乱无章的数据&#xff0c;你需要从中找到特定的信息&#xff0c;或者按照一定的规则对这些数据进行排序。又或者&#xff0c;你要为一个物流公司规划最佳的配送路线&#xff0c;以降低成本和提高效率。这些问题看似复杂&#xff0c;但都可以…...

Mysql--重点篇--索引(索引分类,Hash和B-tree索引,聚簇和非聚簇索引,回表查询,覆盖索引,索引工作原理,索引失效,索引创建原则等)

索引是数据库中用于加速查询操作的重要机制。通过索引&#xff0c;MySQL可以快速定位到满足查询条件的数据行&#xff0c;而不需要扫描整个表。合理的索引设计可以显著提高查询性能&#xff0c;但不合理的索引可能会导致性能下降和磁盘空间浪费。因此&#xff0c;理解索引的工作…...

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 系统中常用的网络管理工具&#xff0c;但它们的设计目标和使用场景不同。以下是它们的详细介绍、功能、使用场景和差异。 1. systemd-networkd systemd-networkd 是一个由 syst…...

本地部署项目管理工具 Leantime 并实现外部访问

Leantime 是一款开源 AI 项目。它可以在本地直接运行大语言模型 LLM、生成图像、音频等。直接降低了用户使用AI的门褴。本文将详细的介绍如何利用 Docker 在本地部署 Leantime 并结合路由侠实现外网访问本地部署的 Leantime 。 第一步&#xff0c;本地部署安装 Leantime 1&am…...

PHP cURL 函数初学者完全指南

文章精选推荐 1 JetBrains Ai assistant 编程工具让你的工作效率翻倍 2 Extra Icons&#xff1a;JetBrains IDE的图标增强神器 3 IDEA插件推荐-SequenceDiagram&#xff0c;自动生成时序图 4 BashSupport Pro 这个ides插件主要是用来干嘛的 &#xff1f; 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 进行开发时&#xff0c;管理应用程序的资源&#xff08;如图标、图片、字体、样式表、音视频等&#xff09;是一个常见的任务。PySide6 提供了一个工具 pyside6-rcc&#xff0c;它能够将资源文件&#xff08;.qrc&#xff09;编译成 Python 模块&#xff0c;然后…...

硬件实用技巧:TPS54331DR横杠标识识别1引脚

若该文为原创文章&#xff0c;转载请注明原文出处 本文章博客地址&#xff1a;https://hpzwl.blog.csdn.net/article/details/145116969 长沙红胖子Qt&#xff08;长沙创微智科&#xff09;博文大全&#xff1a;开发技术集合&#xff08;包含Qt实用技术、树莓派、三维、OpenCV…...

《C++11》nullptr介绍:从NULL说起

在C11之前&#xff0c;我们通常使用NULL来表示空指针。然而&#xff0c;NULL在C中有一些问题和限制&#xff0c;这就是C11引入nullptr的原因。本文将详细介绍nullptr的定义、用法和优点。 1. NULL的问题 在C中&#xff0c;NULL实际上是一个整数0&#xff0c;而不是一个真正的…...

自然语言处理基础:全面概述

自然语言处理基础&#xff1a;全面概述 什么是NLP及其重要性、NLP的核心组件、NLU与NLG、NLU与NLG的集成、NLP的挑战以及NLP的未来 自然语言处理&#xff08;NLP&#xff09;是人工智能&#xff08;AI&#xff09;中最引人入胜且具有影响力的领域之一。它驱动着我们日常使用的…...

(LeetCode 每日一题) 3442. 奇偶频次间的最大差值 I (哈希、字符串)

题目&#xff1a;3442. 奇偶频次间的最大差值 I 思路 &#xff1a;哈希&#xff0c;时间复杂度0(n)。 用哈希表来记录每个字符串中字符的分布情况&#xff0c;哈希表这里用数组即可实现。 C版本&#xff1a; class Solution { public:int maxDifference(string s) {int a[26]…...

rknn优化教程(二)

文章目录 1. 前述2. 三方库的封装2.1 xrepo中的库2.2 xrepo之外的库2.2.1 opencv2.2.2 rknnrt2.2.3 spdlog 3. rknn_engine库 1. 前述 OK&#xff0c;开始写第二篇的内容了。这篇博客主要能写一下&#xff1a; 如何给一些三方库按照xmake方式进行封装&#xff0c;供调用如何按…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?

论文网址&#xff1a;pdf 英文是纯手打的&#xff01;论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误&#xff0c;若有发现欢迎评论指正&#xff01;文章偏向于笔记&#xff0c;谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

如何在看板中有效管理突发紧急任务

在看板中有效管理突发紧急任务需要&#xff1a;设立专门的紧急任务通道、重新调整任务优先级、保持适度的WIP&#xff08;Work-in-Progress&#xff09;弹性、优化任务处理流程、提高团队应对突发情况的敏捷性。其中&#xff0c;设立专门的紧急任务通道尤为重要&#xff0c;这能…...

C++ 求圆面积的程序(Program to find area of a circle)

给定半径r&#xff0c;求圆的面积。圆的面积应精确到小数点后5位。 例子&#xff1a; 输入&#xff1a;r 5 输出&#xff1a;78.53982 解释&#xff1a;由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982&#xff0c;因为我们只保留小数点后 5 位数字。 输…...

uniapp中使用aixos 报错

问题&#xff1a; 在uniapp中使用aixos&#xff0c;运行后报如下错误&#xff1a; AxiosError: There is no suitable adapter to dispatch the request since : - adapter xhr is not supported by the environment - adapter http is not available in the build 解决方案&…...

OpenLayers 分屏对比(地图联动)

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 地图分屏对比在WebGIS开发中是很常见的功能&#xff0c;和卷帘图层不一样的是&#xff0c;分屏对比是在各个地图中添加相同或者不同的图层进行对比查看。…...

wpf在image控件上快速显示内存图像

wpf在image控件上快速显示内存图像https://www.cnblogs.com/haodafeng/p/10431387.html 如果你在寻找能够快速在image控件刷新大图像&#xff08;比如分辨率3000*3000的图像&#xff09;的办法&#xff0c;尤其是想把内存中的裸数据&#xff08;只有图像的数据&#xff0c;不包…...

如何应对敏捷转型中的团队阻力

应对敏捷转型中的团队阻力需要明确沟通敏捷转型目的、提升团队参与感、提供充分的培训与支持、逐步推进敏捷实践、建立清晰的奖励和反馈机制。其中&#xff0c;明确沟通敏捷转型目的尤为关键&#xff0c;团队成员只有清晰理解转型背后的原因和利益&#xff0c;才能降低对变化的…...

mac:大模型系列测试

0 MAC 前几天经过学生优惠以及国补17K入手了mac studio,然后这两天亲自测试其模型行运用能力如何&#xff0c;是否支持微调、推理速度等能力。下面进入正文。 1 mac 与 unsloth 按照下面的进行安装以及测试&#xff0c;是可以跑通文章里面的代码。训练速度也是很快的。 注意…...