力扣--从前序与中序遍历序列构造二叉树

news/2024/4/21 13:50:53/文章来源:https://blog.csdn.net/sweet_Mary/article/details/136546143

题目:

思想:

首先先序遍历能确定根节点的值,此时查看该值在中序遍历中的位置(如果索引为i),那么i左侧为左子树,i 右侧为右子树。从中序数组中即可看出左子树结点个数为 i,右子树节点个数为inorder.size()-i-1。也就代表先序数组中除了第一个元素外,先 i 个元素是左子树对应的先序数组元素,后面的元素为右子树对应的先序数组元素。递归的形式就出现啦!如果没想到可以看一下函数的参数。

代码如下:

C++:

/*** Definition for a binary tree node.* 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) {}* };*/
class Solution {
public:TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {if(preorder.size()==0){return nullptr;}TreeNode* head=new TreeNode;head->val=preorder[0];int idx=find(inorder.begin(),inorder.end(),preorder[0])-inorder.begin();//preorder---左子树vector<int>::const_iterator Firstprel=preorder.begin()+1;vector<int>::const_iterator Secondprel=preorder.begin()+idx+1;vector<int> prel;prel.assign(Firstprel,Secondprel);//preorder---右子树vector<int>::const_iterator Firstprer=preorder.begin()+idx+1;vector<int>::const_iterator Secondprer=preorder.end();vector<int> prer;prer.assign(Firstprer,Secondprer);//inorder---左子树vector<int>::const_iterator Firstinl=inorder.begin();vector<int>::const_iterator Secondinl=inorder.begin()+idx;vector<int> inl;inl.assign(Firstinl,Secondinl);//inorder---右子树vector<int>::const_iterator Firstinr=inorder.begin()+idx+1;vector<int>::const_iterator Secondinr=inorder.end();vector<int> inr;inr.assign(Firstinr,Secondinr);head->left=buildTree(prel,inl);head->right=buildTree(prer,inr);return head;}
};

注意看一下这里的写法:

int idx=find(inorder.begin(),inorder.end(),preorder[0])-inorder.begin();

参考博文:(在inorder中寻找preorder[0]这个元素,返回其索引值)

c++vector查找元素所在的索引下标_vector查找元素索引-CSDN博客 

//preorder---左子树
vector<int>::const_iterator Firstprel=preorder.begin()+1;
vector<int>::const_iterator Secondprel=preorder.begin()+idx+1;
vector<int> prel;
prel.assign(Firstprel,Secondprel);

参考博文:(就是把preorder中的第一个元素直到第idx个元素,复制给prel)

vector 切片,截取指定区间元素_vector截取-CSDN博客

Python:

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:if len(preorder)==0:return Nonehead=TreeNode(preorder[0])idx=inorder.index(preorder[0])prel=preorder[1:idx+1]prer=preorder[idx+1:]inl=inorder[:idx+1]inr=inorder[idx+1:]head.left=self.buildTree(prel,inl)head.right=self.buildTree(prer,inr)return head

注意这样几个写法:

Python中的空指针为None

Python中的创建实例

head=TreeNode(preorder[0])

Python中的从inorder中寻找preorder[0],并返回索引

idx=inorder.index(preorder[0])

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.luyixian.cn/news_show_997380.aspx

如若内容造成侵权/违法违规/事实不符,请联系dt猫网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Pytorch学习 day06(torchvision中的datasets、dataloader)

torchvision的datasets 使用torchvision提供的数据集API&#xff0c;比较方便&#xff0c;如果在pycharm中下载很慢&#xff0c;可以URL链接到迅雷中进行下载&#xff08;有些URL链接在源码里&#xff09;代码如下&#xff1a; import torchvision # 导入 torchvision 库 # …

线程池不香了? 结构化并发才是王道!

我们先定义获取用户信息任务&#xff1a; 再定义获取订单信息任务&#xff1a; 然后再构造线程池并执行任务&#xff1a; 输出结果为&#xff1a; 看上去一切都刚刚好&#xff0c;但是&#xff0c;如果获取订单信息时出错了&#xff0c;此时会是什么现象呢&#xff1f;修改获取…

PoC免写攻略

在网络安全领域&#xff0c;PoC&#xff08;Proof of Concept&#xff09;起着重要的作用&#xff0c;并且在安全研究、漏洞发现和漏洞利用等方面具有重要的地位。攻击方视角下&#xff0c;常常需要围绕 PoC 做的大量的工作。常常需要从手动测试开始编写 PoC&#xff0c;再到实…

SAP - 采购价格确定 ③ 抬头条件和组条件

抬头条件和组条件 当我们创建一个具有多个行项目的采购订单时,我们经常需要条件可以应用到所有的行项目中。相应的,条件也可以应用到特定的行项目。在R/3系统中,条件可以涉及采购凭证的单个行项目(项目条件),多个行项目(组条件)或所有的行项目(抬头条件)。 一些标准…

计算机/大数据毕业设计-基于Python的动漫数据分析可视化系统的设计与实现

基于Python的动漫数据分析可视化系统的设计与实现 设计爬虫程序爬取哔哩哔哩动漫数据信息 后端使用flask框架&#xff0c;数据库使用Mysql8.0&#xff0c;可视化使用echarts 部分代码如下&#xff1a; # 保存所有动漫信息 all_anime_infos [] # 保存到文件中 file_writer …

讨论:5万官网是建站界的劳斯莱斯了吧,到了软件开发领域呢?

如题&#xff0c;所以赛道选择很重要&#xff0c;当然难度系数也不一样。能花5万元做官网的&#xff0c;凤毛麟角&#xff0c;如果是做软件开发&#xff0c;5万元顶多算个起步价&#xff0c;老铁们&#xff0c;是这样吗&#xff1f;

Openwrt(IstoreOS)安装iventoy

背景 目前家里有两台不用的旧主机&#xff0c;平时没事在家里折腾这两台机器。经常换装各种系统。最早是将镜像刷入u盘作为启动盘&#xff0c;这样需要重复装系统就特别麻烦。后来用了ventoy以后一个U盘可以放多个系统镜像&#xff0c;还能做口袋系统&#xff08;SystemToGo&a…

安卓手机如何使用JuiceSSH实现公网远程连接本地Linux服务器

文章目录 1. Linux安装cpolar2. 创建公网SSH连接地址3. JuiceSSH公网远程连接4. 固定连接SSH公网地址5. SSH固定地址连接测试 处于内网的虚拟机如何被外网访问呢?如何手机就能访问虚拟机呢? cpolarJuiceSSH 实现手机端远程连接Linux虚拟机(内网穿透,手机端连接Linux虚拟机) …

别再找了,关于免费SSL证书都在这里

免费SSL证书的优点&#xff1a; 成本效益&#xff1a;免费SSL证书可以帮助网站所有者节省资金&#xff0c;特别是对于初创公司或个人网站来说&#xff0c;这是一个很大的优势。提高信任度&#xff1a;通过使用SSL证书&#xff0c;网站可以向访问者展示其对安全性的承诺&#x…

2024/3/7—2575. 找出字符串的可整除数组

代码实现&#xff1a; int* divisibilityArray(char *word, int m, int *returnSize) {int n strlen(word);int *res (int*)malloc(sizeof(int) * n);long cur 0;for (int i 0; i < n; i) {cur (cur * 10 (word[i] - 0)) % m;res[i] (cur 0) ? 1 : 0;}*returnSize …

1-安装rabbitmq

rabbitmq官网&#xff1a; https://www.rabbitmq.com/docs/download 本机环境&#xff1a;mac&#xff0c;使用orbstack提供的docker 使用docker部署rabbitmq docker run -it --rm --name rabbitmq -p 5672:5672 -p 15672:15672 rabbitmq:3.13-management 然后报错&#xf…

基于STC系列单片机实现PNP型三极管S8550驱动共阳数码管或NPN型三极管S8050驱动共阴数码管功能

Digitron.c #include "Digitron.h" //#include "Key.h" #define uchar unsigned char//自定义无符号字符型为uchar #define uint unsigned int//自定义无符号整数型为uint //uchar code DigitronBitCodeArray[] {0x01,0x02,0x04,0x08,0x10,0x20,0x40,0x8…

机器学习-面经(part8、贝叶斯和其他知识点)

机器学习面经其他系列 机器学习面经系列的其他部分如下所示&#xff1a; 机器学习-面经(part1)-初步说明 机器学习-面经(part2)-交叉验证、超参数优化、评价指标等内容 机器学习-面经(part3)-正则化、特征工程面试问题与解答合集机器学习-面经(part4)-决策树共5000字的面试问…

go linux监测文件变化

go linux监测文件变化 文件改变内容有两种方式&#xff0c;效果一样&#xff0c;但执行方式有区别: 直接打开文件改&#xff0c;现在很多编辑器都是这样操作的先删除原来的&#xff0c;再新创建写入一个替代原来的。比如vi/vim.这种方式会打断linux inotify原有的监测(就好比…

springboot+vue+mysql项目使用的常用注解

实体类常用注解 Data Data 是一个 Lombok 提供的注解&#xff0c;使用 Data 注解可以简化代码&#xff0c;使代码更加简洁易读。 作用&#xff1a;自动为类生成常用的方法&#xff0c;包括 getter、setter、equals、hashCode 和 toString 等需要加Lombok的依赖 <depende…

vue系列——vscode,node.js vue开发环境搭建

第一步安装node.js 推荐使用nvm进行node.js 的安装 nvm(Node.js version manager) 是一个命令行应用&#xff0c;可以协助您快速地 更新、安装、使用、卸载 本机的全局 node.js 版本。 可以去网上查找相关版本 我这里使用 nvm-setu… 链接:https://pan.baidu.com/s/1UEUtmzw5x…

【数据结构】红黑树(RBTree)

介绍 概念 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但在每个结点上增加一个存储位表示结点的颜色&#xff0c;可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制&#xff0c;红黑树确保没有一条路径会比其他路径长出两倍&#xff0c;因而是…

专家解读:2024年十大项目管理工具综合排名与评价

2024年涌现出一批新的项目管理工具&#xff0c;各具特色的功能和设计为企业解决了诸多的管理难题。今天我们就来盘点2024年的十款项目管理工具Zoho Projects、AgileMaster、PlanItAll、CommuniQ、WorkFlowRanger、GanttGenius、RiskAssessor、TeamHarmony、BudgetBoss、CloudCo…

智能控制:物联网智能插座对接文档

介绍 一开始买的某米的插座&#xff0c;但是好像接口不开放&#xff0c;所以找到了这个插座&#xff0c;然后自己开发了下&#xff0c;用接口控制插座开关。wifi的连接方式&#xff0c;通电后一般几秒后就会连接上wifi&#xff0c;这个时候通过接口发送命令给他。 产品图片 通…

#QT(DEMO)

1.IDE&#xff1a;QTCreator 2.实验&#xff1a;打印"hello wolrd" 3.记录 &#xff08;1&#xff09;创建一个新工程&#xff1a; 新建好一个工程存放文件夹&#xff08;路径不能有中文&#xff09;,然后按下图配置 &#xff08;2&#xff09;点击widgets.ui拖入以…