二叉搜索树的特性是,任何一个节点的值:
- 都大于左子树任意节点。
- 都小于右子树任意节点。
因为二叉搜索树的特性,我们可以更高效的应用算法。
精读
还记得 《算法 – 二叉树》 提到的 二叉树的最近公公祖先 问题吗?如果这是一颗二叉搜索树,是不是存在更巧妙的解法?你可以暂停先思考一下。
二叉搜索树的最近公共祖先
二叉搜索树的最近公共祖先是一道简单题,题目如下:
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树
T
的两个结点p
、q
,最近公共祖先表示为一个结点x
,满足x
是p
、q
的祖先且x
的深度尽可能大(一个节点也可以是它自己的祖先)。”
第一个判断条件是相同的,即当前节点值等于 p
或 q
任意一个,则当前节点就是其最近公共祖先。
如果不是呢?同时考虑二叉搜索树与公共祖先的特性可以发现:
- 如果
p
q
两个节点分别位于当前节点的左 or 右边,则当前节点符合要求。 - 如果
p
q
值一个大于,一个小于当前节点,说明p
q
分布在当前节点左右两侧。
基于以上考虑,可以仅通过值大小来判断,因此题目就被简化了。
接下来看一道入门题,即如何验证一颗二叉树是二叉搜索树。
验证二叉搜索树
验证二叉搜索树是一道中等题,题目如下:
给定一个二叉树,判断其是否是一个有效的二叉搜索树。
假设一个二叉搜索树具有如下特征:
- 节点的左子树只包含小于当前节点的数。
- 节点的右子树只包含大于当前节点的数。
- 所有左子树和右子树自身必须也是二叉搜索树。
这道题看上去就应该用非常优雅的递归来实现。
二叉搜索树最重要的就是对节点值的限制,我们如果能正确卡住每个节点的值,就可以判断了。
如何判断节点值是否正确呢?我们可以用递归的方式倒推,即从根节点开始,假设根节点值为 x
,那么左树节点的值就必须小于 x
,再往左,那么值就要小于(假设第一个左节点值为 x1
) x1
,右树也是一样判断,因此就可以写出答案:
function isValidBST(node: TreeNode, min = -Infinity, max = Infinity) {
if (node === null) return true
// 判断值范围是否合理
if (node.val < min || node.val > max) return false
// 继续递归,并且根据二叉搜索树特定,进一步缩小最大、最小值的锁定范围
return
// 左子树值 max 为当前节点值
isValidBST(node.left, min, node.val) &&
// 右子树值 min 为当前节点值
isValidBST(node.right, node.val, max) &&
}
接下来看一些简单的二叉搜索树操作问题,比如删除二叉搜索树中的节点。
删除二叉搜索树中的节点
删除二叉搜索树中的节点是一道中等题,题目如下:
给定一个二叉搜索树的根节点 root 和一个值 key,删除二叉搜索树中的 key 对应的节点,并保证二叉搜索树的性质不变。返回二叉搜索树(有可能被更新)的根节点的引用。
一般来说,删除节点可分为两个步骤:
- 首先找到需要删除的节点;
- 如果找到了,删除它。
说明: 要求算法时间复杂度为
O(h)
,h
为树的高度。
要删除二叉搜索树的节点,找到节点本身并不难,因为如果值小了,就从左子树找;如果值大了,就从右子树找,这本身查找起来是非常简单的。难点在于,如何保证删除元素后,这棵树还是一颗二叉搜索树?
假设我们删除的是叶子结点,很显然,二叉搜索树任意子树都是二叉搜索树,我们又没有破坏其他节点的关系,因此直接删除就行了,最简单。
如果删除的不是叶子结点,那么谁来 “上位” 代替这个节点呢?题目要求复杂度为 O(h)
显然不能重新构造,我们需要仔细考虑。
假设删除的节点存在右节点,那么肯定从右节点找到一个代替值移上来,找谁呢?找右节点的最小值呀,最小值很好找的,找完代替后,相当于 问题转移为删除这个最小值节点,递归就完事了。
假设删除的节点存在左节点,但是没有右节点,那就从左节点找一个最大的替换掉,同理递归删除找到的节点。
可以看到,删除二叉搜索树,为了让二叉搜索树性质保持不变,需要不断进行重复子问题的递归删除节点。
当你掌握二叉搜索树特性后,可以尝试构造二叉搜索树了,下面就是一道让你任意构造二叉搜索树的题目:不同的二叉搜索树。
不同的二叉搜索树
不同的二叉搜索树是一道中等题,题目如下:
给你一个整数
n
,求恰由n
个节点组成且节点值从1
到n
互不相同的 二叉搜索树 有多少种?返回满足题意的二叉搜索树的种数。
这道题重点在于动态规划思维 + 笛卡尔积组合的思维。
需要将所有可能性想象为确定了根节点后,左右子树到底有几种组合方式?
举个例子,假设 n=10
,那么这 10 个节点,假设我取第 3 个节点为根节点,那么左子树有 2 个节点,右子树有 7 个节点,这种组合情况就有 DP(2) * DP(7)
这么多,假设 DP(n)
表示 n 个节点能组成任意二叉搜索树的数量。
这仅是第 3 个节点为根节点的情况,实际上每个节点作为根节点都是不同的树(轴对称也算不同的),那么我们就要从第 1 个节点计算到第 n
个节点。
因此答案就出来了,我们先考虑特殊情况 DP(0)=1
DP(1)=1
,所以:
function numTrees(n: number) {
const dp: number[] = [1, 1]
for (let i = 2; i <= n; i++) {
for (let j = 1; j <= i; j++) {
dp[i] += dp[j - 1] * dp[i - j]
}
}
return dp[n]
}
最后再看一道找值题,并不是找最大值,而是找第 k 大值。
二叉搜索树的第 K 大节点
二叉搜索树的第 K 大节点是一道简单题,题目如下:
给定一棵二叉搜索树,请找出其中第
k
大的节点。
这道题之所以简单,是因为二叉搜索树的中序遍历是从小到大的,因此只要倒序中序遍历,就可以找到第 k
大的节点。
倒序中序遍历,即右、根、左。
这道题就解决啦。
总结
二叉搜索树的特性很简单,就是根节点值夹在左右子树中间,利用这个特性几乎可以解决一切相关问题。
但通过上面几个例子可以发现,仅熟悉二叉搜索树特性还是不够的,一些题目需要结合二叉树中序遍历、公共祖先特征等通用算法思路结合来解决,因此学会融会贯通很重要。
1、本站所有资源均从互联网上收集整理而来,仅供学习交流之用,因此不包含技术服务请大家谅解!
2、本站不提供任何实质性的付费和支付资源,所有需要积分下载的资源均为网站运营赞助费用或者线下劳务费用!
3、本站所有资源仅用于学习及研究使用,您必须在下载后的24小时内删除所下载资源,切勿用于商业用途,否则由此引发的法律纠纷及连带责任本站和发布者概不承担!
4、本站站内提供的所有可下载资源,本站保证未做任何负面改动(不包含修复bug和完善功能等正面优化或二次开发),但本站不保证资源的准确性、安全性和完整性,用户下载后自行斟酌,我们以交流学习为目的,并不是所有的源码都100%无错或无bug!如有链接无法下载、失效或广告,请联系客服处理!
5、本站资源除标明原创外均来自网络整理,版权归原作者或本站特约原创作者所有,如侵犯到您的合法权益,请立即告知本站,本站将及时予与删除并致以最深的歉意!
6、如果您也有好的资源或教程,您可以投稿发布,成功分享后有站币奖励和额外收入!
7、如果您喜欢该资源,请支持官方正版资源,以得到更好的正版服务!
8、请您认真阅读上述内容,注册本站用户或下载本站资源即您同意上述内容!
原文链接:https://www.dandroid.cn/17872,转载请注明出处。
评论0