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

本文主要是介绍算法题解记录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的一些知识。

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

这篇关于算法题解记录11+++从前序与中序遍历序列构造二叉树(百日筑基)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/903350

相关文章

Python UV安装、升级、卸载详细步骤记录

《PythonUV安装、升级、卸载详细步骤记录》:本文主要介绍PythonUV安装、升级、卸载的详细步骤,uv是Astral推出的下一代Python包与项目管理器,主打单一可执行文件、极致性能... 目录安装检查升级设置自动补全卸载UV 命令总结 官方文档详见:https://docs.astral.sh/

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》:本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题:在生产上导入的数据发现

统一返回JsonResult踩坑的记录

《统一返回JsonResult踩坑的记录》:本文主要介绍统一返回JsonResult踩坑的记录,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录统一返回jsonResult踩坑定义了一个统一返回类在使用时,JsonResult没有get/set方法时响应总结统一返回

Go学习记录之runtime包深入解析

《Go学习记录之runtime包深入解析》Go语言runtime包管理运行时环境,涵盖goroutine调度、内存分配、垃圾回收、类型信息等核心功能,:本文主要介绍Go学习记录之runtime包的... 目录前言:一、runtime包内容学习1、作用:① Goroutine和并发控制:② 垃圾回收:③ 栈和

java对接海康摄像头的完整步骤记录

《java对接海康摄像头的完整步骤记录》在Java中调用海康威视摄像头通常需要使用海康威视提供的SDK,下面这篇文章主要给大家介绍了关于java对接海康摄像头的完整步骤,文中通过代码介绍的非常详细,需... 目录一、开发环境准备二、实现Java调用设备接口(一)加载动态链接库(二)结构体、接口重定义1.类型

apache的commons-pool2原理与使用实践记录

《apache的commons-pool2原理与使用实践记录》ApacheCommonsPool2是一个高效的对象池化框架,通过复用昂贵资源(如数据库连接、线程、网络连接)优化系统性能,这篇文章主... 目录一、核心原理与组件二、使用步骤详解(以数据库连接池为例)三、高级配置与优化四、典型应用场景五、注意事

SpringBoot实现文件记录日志及日志文件自动归档和压缩

《SpringBoot实现文件记录日志及日志文件自动归档和压缩》Logback是Java日志框架,通过Logger收集日志并经Appender输出至控制台、文件等,SpringBoot配置logbac... 目录1、什么是Logback2、SpringBoot实现文件记录日志,日志文件自动归档和压缩2.1、

qtcreater配置opencv遇到的坑及实践记录

《qtcreater配置opencv遇到的坑及实践记录》我配置opencv不管是按照网上的教程还是deepseek发现都有些问题,下面是我的配置方法以及实践成功的心得,感兴趣的朋友跟随小编一起看看吧... 目录电脑环境下载环境变量配置qmake加入外部库测试配置我配置opencv不管是按照网上的教程还是de

利用Python实现时间序列动量策略

《利用Python实现时间序列动量策略》时间序列动量策略作为量化交易领域中最为持久且被深入研究的策略类型之一,其核心理念相对简明:对于显示上升趋势的资产建立多头头寸,对于呈现下降趋势的资产建立空头头寸... 目录引言传统策略面临的风险管理挑战波动率调整机制:实现风险标准化策略实施的技术细节波动率调整的战略价

python进行while遍历的常见错误解析

《python进行while遍历的常见错误解析》在Python中选择合适的遍历方式需要综合考虑可读性、性能和具体需求,本文就来和大家讲解一下python中while遍历常见错误以及所有遍历方法的优缺点... 目录一、超出数组范围问题分析错误复现解决方法关键区别二、continue使用问题分析正确写法关键点三