算法题解记录11+++从前序与中序遍历序列构造二叉树(百日筑基)

题目描述:

        给定两个整数数组 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.了解二叉树:二叉树是递归定义的,当其根节点root!=null时,它有以下性质:root有且仅有两颗子树,分别是左子树left和右子树right。如果把left看成树(left!=null,不过实际也是一棵树),那么其左子树也是一棵二叉树,同理,右子树right也是。

        2.了解二叉树前序、中序遍历:二叉树DFS深度优先算法有前序、中序和后序三种,其“序”的概念针对于根节点root。对于前序:root->left->right,也就是根节点、左子树、右子树;对于中序:即左子树、根节点、右子树。

        3.猜测可能存在的基础操作:由于需要构造二叉树,而且提供的是两个数组(前序遍历数组、中序遍历数组),所以大概率需要进行“添加”这一基础操作(勉强算是吧)。由于提供只两个数组,感觉可能要遍历。。所以初步认为可能有遍历、添加两个基础操作。

        4.模拟操作:

                对于下图的二叉树,我们可能轻松得到其前序、中序遍历数组(当然了,这是输入,是已知条件)

                那好像看不出什么操作:从定义开始,先寻找一下两个数组的关系。

解题难点1分析:

        难点1:如何分步操作,构造这棵二叉树?

        从定义出发,我们知道:

        1.前序数组是:【根节点,左子树,右子树】

        2.中序数组是:【左子树,根节点,右子树】

        那么,我们可以通过二者的相互关系,得到左子树前序、中序遍历数组。

        可是好像没什么用?拿到左子树的遍历数组(把它当成独立的树),好像又回到原来的问题:怎么分步构造树?

        我们知道,在左子树前、中序遍历中,一定也存在根节点,并且在前序遍历中,第一个节点就是根节点。

        那,这个性质怎么用?

        我们先了解两件事:

        1.二叉树由递归构造。

        2.对于一棵树,其所有基础操作都要落到具体的节点上,如果拿不到具体节点,什么都是假的。

        我们认为题目提供的函数已经具备构造二叉树的能力。

        也就是说,既然题目提供了前序、中序数组就能得到二叉树,不如我们借助递归去利用这个函数。

        因此,对于树root、left、right,我们把left的前、中序遍历数组,作为函数参数传递。

        不过问题来了:传递了第一遍,就没法拿到左子树left的左子树了。而且另一个问题是,前序、中序数组的构造也是个麻烦,每一个节点的左、右子树的长度不一定一样。

        也许是缺参数了,如果我们可以提供左、右子树的长度,在进行传递,就可以了?

        不行,这一步反而陷入重复论证,因为我们如果可以构造一个左子树(或右子树)数组,那么就一定知道其长度。(left.length)。

        不过我们记得:二叉树递归定义,所以其前序、中序遍历也具有递归性,对于左子树的前序遍历序列,有:

        left:【根节点left,left的左子树,left的右子树】

        把它放进根节点root中,有:【root,【(左子树)left,left左子,left右子】,右子树同理】

        也就是说,题目提供的前序、中序遍历数组,其中就包含了某个节点的前、中序遍历。

        所以,我们的问题就转换为:如何从题目提供的数组中,拿到某个节点的前、中序遍历。

        通过双指针(指向数组)就可以了,既然其具有递归性,那么某个节点的前、中序遍历是连续的(我指的是,数组中的元素连续,比如【1,2,3,4,5】,“1,2,3”连续,“1,3”不连续)

        对前序数组,用一个双指针,对中序数组,再用一个双指针,一共4个变量,就可以覆盖数据。

        因此,我们的新函数X,需要6个参数,前、中序遍历数组,4个指针。

        不过问题又来了:要怎么构造树呢?

        我们已经可以针对某个节点,得到其前、中序遍历,那么,就可以一直递归到该节点是叶子节点的时候。

        对于某个节点A,A如果是叶子节点,那么它返回其本身即可。

        A如果有子树,那么需要把子树连接到其确定位置。

        对于函数X,我们认为其具备构造二叉树的能力,只要提供给X一棵树的前、中序遍历,X就可以返回这棵树的根节点。

        因此,A有子树,如果是左子树,把左子树的前、中序遍历提供给X,然后A.left=X()即可。

        右子树同理。

        那么,如何拿到左右子树?

        1.前序:根、左、右,第一个一定是根。

        2.中序:左、根、右,拿到根,就可确定左、右子树(的长度),然后……

        由于数组不存在重复元素,所以不会出错。

        如果从前序拿到根,然后在中序中遍历,速度较慢,可以用哈希表。

代码:

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {Map<Integer, Integer> index; // 这里需要注意,如果没写泛型,默认为object,可能出错public TreeNode buildTree(int[] preorder, int[] inorder) {index=new HashMap<Integer, Integer>();int n=inorder.length;for(int i=0; i<n; i++){index.put(inorder[i], i); // 提供一个快速搜索的方式,用数组搜索也一样。}return myBuild(preorder, inorder, 0, n-1, 0, n-1);}// 递归调用private TreeNode myBuild(int[] preorder, int[] inorder, int pre_left,int pre_right, int in_left, int in_right){// 叶子节点,因为叶子节点的前、中序遍历数组为nullif(pre_right<pre_left){return null;}int root_val=preorder[pre_left]; // 得到根节点的值 int in_root=index.get(root_val); // 从中序遍历数组,拿到根节点下标int len=in_root-in_left; // 拿到节点A的遍历数组的长度TreeNode root=new TreeNode(root_val); // 实例化根节点(该根节点并非题解的根节点)root.left=myBuild(preorder, inorder, pre_left+1, pre_left+len,in_left, in_root-1); // 递归调用,前序遍历第一个是根节点,所以加1,加len是因为前、中序遍历长度相同,由于中序先是左子树,所以从left到根节点-1root.right=myBuild(preorder, inorder, pre_left+len+1, pre_right,in_root+1, in_right); // 递归调用,想拿到右子树,那么得从左子树末尾开始,后面都是右子树,所以是pre_right。中序是左根右,所以从根+1到in_rightreturn root;}
}

以上内容即我想分享的关于力扣热题11的一些知识。

        我是蚊子码农,如有补充,欢迎在评论区留言。个人也是初学者,知识体系可能没有那么完善,希望各位多多指正,谢谢大家。

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

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

相关文章

网上订餐系统|基于springboot的网上订餐系统设计与实现(源码+数据库+文档)

网上订餐系统目录 目录 基于springboot的网上订餐系统设计与实现 一、前言 二、系统功能设计 三、系统实现 1、用户功能模块的实现 &#xff08;1&#xff09;用户注册界面 &#xff08;2&#xff09;用户登录界面 &#xff08;3&#xff09;菜品详情界面 &#xff08…

解决Error (169281)、Error (169282)报错问题,QuartusII设置Virtual Pin虚拟管脚的详细操作方法

解决Error(169281)、Error(169282)报错问题,QuartusII设置Virtual Pin虚拟管脚的详细操作方法 1,QuartusII报错信息2,解决办法3,重新编译,成功参考文献: 1,Quartus如何设置虚拟管脚Virtual Pin(具体设置方法) 1,QuartusII报错信息 报错原因:    为了验证FPGA工…

vue学习日记22:非父子通信(拓展)-provideinject

一、概念 二、实践 代码 App <template><div class"app">我是APP组件<button click"change">修改数据</button><SonA></SonA><SonB></SonB></div> </template><script> import SonA …

5个常见的前端手写功能:New、call apply bind、防抖和节流、instanceof、ajax

实现New 首先创建一个新的空对象设置原型&#xff0c;将对象的原型设置为函数的prototype对象让函数的this指向这个对象&#xff0c;执行构造函数的代码判断函数的返回值类型&#xff0c;如果是值类型&#xff0c;返回创建的对象。如果是引用类型&#xff0c;就返回这个引用类…

UE5 C++ 射线检测

一.声明四个变量 FVector StartLocation;FVector ForwardVector;FVector EndLocation;FHitResult HitResult;二.起点从摄像机&#xff0c;重点为摄像机前9999m。射线检测 使用LineTraceSingleByChannel 射线直线通道检测&#xff0c;所以 void AMyCharacter::Tick(float Delt…

9、statefulSet 有状态pod

1、statefulSet与replicationController、replicaSet的区别 1.1 有无状态 statefulSet是有状态的&#xff0c;类似于数据库、配置中心等&#xff0c;移除后需要创建相同的pod rc与rs是无状态的&#xff0c;可替换的 1.2 命名规则 1.3创建规则 statefulSet修改完ymal文件&…

GVRP协议与动态、静态vlan

一、GVRP协议使用场景 1、当实际组网复杂到网络管理员无法短时间内了解网络的拓扑结构&#xff0c;或者是整个网络的VLAN太多时&#xff0c;工作量会非常大&#xff0c;而且非常容易配置错误。在这种情况下&#xff0c;用户可以通过GVRP的VLAN自动注册功能完成VLAN的配置。 2、…

HarmonyOS开发实例:【分布式数据管理】

介绍 本示例展示了在eTS中分布式数据管理的使用&#xff0c;包括KVManager对象实例的创建和KVStore数据流转的使用。 通过设备管理接口[ohos.distributedDeviceManager]&#xff0c;实现设备之间的kvStore对象的数据传输交互&#xff0c;该对象拥有以下能力 ; 1、注册和解除注…

Compose 简单组件

文章目录 Compose 简单组件TextText属性使用AnnotatedStringSpanStyleParagraphStyle SelectionContainer 和 DisableSelectionClickableText TextFieldTextField属性使用OutlinedTextFieldBasicTextFieldKeyboardOptions 键盘属性KeyboardActions IME动作 ButtonButton属性使用…

基于SpringBoot+Vue的校园商铺管理系统设计与实现(源码+文档+包运行)

一.系统概述 信息数据从传统到当代&#xff0c;是一直在变革当中&#xff0c;突如其来的互联网让传统的信息管理看到了革命性的曙光&#xff0c;因为传统信息管理从时效性&#xff0c;还是安全性&#xff0c;还是可操作性等各个方面来讲&#xff0c;遇到了互联网时代才发现能补…

中铁建智能安全帽与统一视频平台smarteye配奥维地图是否绝配?

中铁建智能安全帽与统一视频平台smarteye配奥维地图是否绝配&#xff1f; 在电厂、煤矿等厂矿企业内部&#xff0c;施工、抢修&#xff0c;临抢任务等场合下&#xff0c;都需要智能安全帽的实时图传和地图定位功能&#xff0c;相比较传统的高德/百度地图&#xff0c;奥维地图在…

黄仁勋最新访谈:GPU性能的革命性提升与AI未来

近期&#xff0c;英伟达CEO黄仁勋与美国CNBC知名主持人、股评人吉姆克莱默&#xff08;Jim Cramer&#xff09;在《Mad Money》节目中展开了一场关于技术未来和人工智能的对话。访谈里&#xff0c;黄仁勋不仅提到了英伟达在过去八年中将AI算力性能提高1000倍&#xff0c;还预言…

HarmonyOS实战开发-横竖屏切换

介绍 本实例展示如何使用媒体查询&#xff0c;通过ohos.mediaquery 接口完成在不同设备上显示不同的界面效果。 效果预览 使用说明 1.在竖屏设备上&#xff0c;首页展示新闻列表&#xff0c;点击新闻进入详情界面。 2.在横屏设备上&#xff0c;首页左侧展示新闻列表&#x…

Learn something about front end——颜色

​ 好装的标题啊哈哈哈哈哈哈 最近get了一个学习前端的网站叫FreeCodeCamp 原色&#xff1a;rgb三个值的其中一个值拉满&#xff0c;比如说rgb(255,0,0)是红色这样&#xff0c;三个主色&#xff1a; 红色 rgb(255, 0, 0) #FF0000绿色 rgb(0, 255, 0) #00FF00蓝色 rgb(0, 0, …

GAN:对抗生成网络【通俗易懂】

一、概述 对抗生成网络&#xff08;GAN&#xff09;是一种深度学习模型&#xff0c;由两个神经网络组成&#xff1a;生成器G和判别器D。这两个网络被训练来协同工作&#xff0c;以生成接近真实数据的新样本。 生成器的任务是接收一个随机噪声向量&#xff0c;并将其转换为与真…

鸿蒙语言TypeScript学习第18天:【泛型】

1、TypeScript 泛型 泛型&#xff08;Generics&#xff09;是一种编程语言特性&#xff0c;允许在定义函数、类、接口等时使用占位符来表示类型&#xff0c;而不是具体的类型。 泛型是一种在编写可重用、灵活且类型安全的代码时非常有用的功能。 使用泛型的主要目的是为了处…

SqlServer快速导出数据库结构的方法

1、查询出所有的表 SELECT name, id From sysobjects WHERE xtype u ORDER BY name ASC 2、根据表名查询出表结构 select syscolumns.name as "列名", systypes.name as "数据类型", syscolumns.length as "数据长度", sys.extended_prope…

prompt 工程整理(未完、持续更新)

工作期间会将阅读的论文、一些个人的理解整理到个人的文档中&#xff0c;久而久之就积累了不少“个人”能够看懂的脉络和提纲&#xff0c;于是近几日准备将这部分略显杂乱的内容重新进行梳理。论文部分以我个人的理解对其做了一些分类&#xff0c;并附上一些简短的理解&#xf…

【Golang】并发编程之三大问题:原子性、有序性、可见性

目录 一、前言二、概念理解2.1 有序性2.2 原子性后果1&#xff1a;其它线程会读到中间态结果&#xff1a;后果2&#xff1a;修改结果被覆盖 2.3 可见性1&#xff09;store buffer(FIFO)引起的类似store-load乱序现象2&#xff09;store buffer(非FIFO)引起的类似store-store乱序…

Netty学习——实战篇4 Netty开发Http服务实战、ByteBuf使用、开发群聊系统 备份

1 Netty开发Http服务实战 &#xff08;1&#xff09;Netty服务器监听8000端口&#xff0c;浏览器发出请求“http://localhost:8000” &#xff08;2&#xff09;服务器可以回复消息给客户端&#xff0c;“你好&#xff0c;我是服务器”,并对特定请求资源进行过滤。 HttpServer…