建设网站需要的技术,网架结构厂家电话,如何开一家网站建设公司,wordpress为什么排名不好今日题目#xff1a; 654. 最大二叉树105. 从前序与中序遍历序列构造二叉树106. 从中序与后序遍历序列构造二叉树889. 根据前序和后序遍历构造二叉树 目录 LC 654. 最大二叉树 【easy】 Problem#xff1a;根据遍历序列来还原二叉树 【classic】 ⭐⭐⭐⭐⭐LC 105. 从前序与中… 今日题目 654. 最大二叉树105. 从前序与中序遍历序列构造二叉树106. 从中序与后序遍历序列构造二叉树889. 根据前序和后序遍历构造二叉树 目录 LC 654. 最大二叉树 【easy】 Problem根据遍历序列来还原二叉树 【classic】 ⭐⭐⭐⭐⭐LC 105. 从前序与中序遍历序列构造二叉树LC 106. 从中序与后序遍历序列构造二叉树LC 889. 根据前序和后序遍历构造二叉树 【稍有难度】 今天主要练习了二叉树的构建的相关题目典型的是从前序、中序、后序遍历的结果中的两个来还原一颗二叉树这类题目的技巧类似同时也是高频考题需要重点掌握。
二叉树的构造问题一般都是使用「分解问题」的思路构造整棵树 根节点 构造左子树 构造右子树。
LC 654. 最大二叉树 【easy】 654. 最大二叉树 这个题目难度不大但这个题经典地体现了使用递归的方法来构建一个二叉树。
Problem根据遍历序列来还原二叉树 【classic】 ⭐⭐⭐⭐⭐
这类题目给出前序、中序、后序遍历的序列中的两个要求来还原二叉树。
要使用分解问题的思路着眼于如何构造一个二叉节点然后递归地构建其左右子树。整体思路大致都是
先从一个序列中确定出根节点的值创建一个根节点利用根节点的值将两个序列切割成两部分然后递归构建左右子树
具体在实现上让我们从例题中具体学习。
LC 105. 从前序与中序遍历序列构造二叉树 105. 从前序与中序遍历序列构造二叉树 这个题目给出了前序遍历和中序遍历的结果让我们还原二叉树。
这类题目首先画出一张图便于我们确定切割的界限 画了这张图后我们就可以知道
preorder 的首元素就是 root利用 root 可以将 inorder 切分出左子树和右子树从而得知左子树的大小 leftSize利用 leftSize就可以将 preorder 也切分成左子树和右子树将切分后的用于递归构建
代码示例 这里有几个关键点
build 函数是主要逻辑所在其参数包括了两个遍历序列及其范围便于通过界定范围来递归构建左右子树先确定 root value构建出 root然后切分遍历序列并递归构建计算出左子树大小 leftSize 对于界定切分范围很有用千万别把递归构建时的范围弄错了。有个验证的小技巧root.left 的 build 中的范围、root、root.right 的 build 的范围这三者应该能够形成一个连续的区间。这个技巧对于检查以及防止多一个少一个这种失误很有用
LC 106. 从中序与后序遍历序列构造二叉树 106. 从中序与后序遍历序列构造二叉树 学会了上一个题目后这个题的套路一样所以难度就不大了。代码上也和上一题差不多 可以看到。套路基本一模一样。
LC 889. 根据前序和后序遍历构造二叉树 【稍有难度】 889. 根据前序和后序遍历构造二叉树 这个题目和前面有点变化了前面两个题目给的序列可以唯一确定出一个二叉树但这个题给的前序和后序无法唯一确定一个二叉树原因就在于尽管我们可以确定出 root value但无法通过 root valule 来进一步切分出序列中的左子树部分和右子树部分。
这个题目解题的诀窍在于我们可以假定一个可以是 left node 的元素作为左子树并利用它来切分序列。例如下面这个示例 我们可以确定 3 是 root value然后我们假定 preorder 中 root 的下一个元素 9 就是 left node尽管它也可能是属于右子树。这种不确定也导致了给定的两个序列无法唯一确定一个二叉树。但幸运的是我们只需要找到合法的一种可能就行所以我们可以做出这种假设。
通过这种假设我们就可以还原一棵二叉树了。这样代码思路也就和前面两个题目一样了。代码如下 可以看出代码架构与之前的几乎一模一样。
