leetcode_day21
本文最后更新于 2024年6月13日 上午
今日任务:
- 530. 二叉搜索树的最小绝对差easy
- 501. 二叉搜索树中的众数easy
- 236. 二叉搜索树的最近公共祖先medium
530. 二叉搜索树的最小绝对差
题目:(仅题干,示例请移步力扣)
给你一个二叉搜索树的根节点 root
,返回
树中任意两不同节点值之间的最小差值
。
差值是一个正数,其数值等于两值之差的绝对值。
思路:
由于是二叉搜索树,时刻牢记中序遍历二叉搜索树相当于遍历有序数组,所以大思路就是中序遍历树,并维护一个最小绝对差
中序遍历这里采用递归法,递归途中需要记录上一个节点的值以求出两数之差
1 |
|
501. 二叉搜索树中的众数
题目:
给你一个含重复值的二叉搜索树(BST)的根节点 root
,找出并返回 BST 中的所有
众数
(即,出现频率最高的元素)。
如果树中有不止一个众数,可以按 任意顺序 返回。
假定 BST 满足如下定义:
- 结点左子树中所含节点的值
小于等于
当前节点的值 - 结点右子树中所含节点的值
大于等于
当前节点的值 - 左子树和右子树都是二叉搜索树
思路:
大思路仍然依靠中序遍历二叉搜索树相当于遍历有序数组,问题转换为求出一个有序数组中的众数,那么在遍历时记录每个数的频率,维护一个最大频率
若该数最后的频率小于最大频率,则不做操作;等于最大频率,则加入答案中;大于最大频率,则更新最大频率,清空当前答案,并将当前数加入答案
依然是递归中序遍历
1 |
|
236. 二叉搜索树的最近公共祖先
题目:
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
思路
初次尝试越想越复杂,以失败告终,原因是单次递归逻辑和终止条件没想明白,
按照carl的递归三部曲:
- 确定递归返回值和参数。这一步没问题,就按照力扣给的核心方法的定义就可以,返回公共祖先的指针,参数就是两个节点p、q和根节点
- 确定递归终止条件。第一个终止条件想到了:“root等于p或者q时,或者root为空”就返回root。之后就开始混乱了,尝试讨论p、q是root的孩子还是孙子还是更远的孩子,遂失败
- 确定单次递归逻辑。失败
我没有分析出:当递归到
最近公共祖先的祖先
时,返回值也应该是最近公共祖先
,也就是说最近公共祖先
是会不断向上传递的,这样就就能保证最近
而不会得到深度更浅的公共祖先。
对于遍历一条路还是遍历整棵树,carl老师的解释令我耳目一新:
在递归函数有返回值的情况下:如果要搜索一条边,递归函数返回值不为空的时候,立刻返回,如果搜索整个树,直接用一个变量left、right接住返回值,这个left、right后序还有逻辑处理的需要,也就是后序遍历中处理中间节点的逻辑(也是回溯)。
搜索一条边的写法: 1
2if (递归函数(root->left)) return ;
if (递归函数(root->right)) return ;1
2
3left = 递归函数(root->left); // 左
right = 递归函数(root->right); // 右
left与right的逻辑处理; // 中
由于返回值确定,所以递归时肯定会有东西接住返回值,又由于,递归的参数是root,返回值也是root,所以当递归root左右孩子时,返回值也应该是左右孩子,即必然会有
left = lowestCommonAncestor(root->left, p, q);
由于这道题不需要对树进行操作,只需要查找遍历,所以left
并不是root->left
,即不需要更新。根据carl的区分,我们可以根据这条语句推断我们之后应该进行left和right的逻辑处理,那么就可以合理推测应该判断left和right是否为空,因为如果没有找到必定返回空,而找到p、q才会返回p或者q,那么如果left和right都返回了,就遇到答案(root)了,向上不断返回即可。
1 |
|
对于想了半小时还WA的我来说,这真是段优雅的代码