leetcode_day21

本文最后更新于 2024年6月13日 上午

今日任务:

530. 二叉搜索树的最小绝对差

题目:(仅题干,示例请移步力扣)

给你一个二叉搜索树的根节点 root ,返回 树中任意两不同节点值之间的最小差值

差值是一个正数,其数值等于两值之差的绝对值。

思路:

由于是二叉搜索树,时刻牢记中序遍历二叉搜索树相当于遍历有序数组,所以大思路就是中序遍历树,并维护一个最小绝对差

中序遍历这里采用递归法,递归途中需要记录上一个节点的值以求出两数之差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
void traversal(TreeNode * root, int &ans, int & pre) {
if(root) {
traversal(root->left, ans, pre);
if(pre == -1) pre = root->val;
else {
ans = min(ans, root->val - pre);
pre = root->val;
}
traversal(root->right, ans, pre);
}
}
int getMinimumDifference(TreeNode* root) {
int ans = INT_MAX, pre = -1;
traversal(root, ans, pre);
return ans;
}
};

501. 二叉搜索树中的众数

题目:

给你一个含重复值的二叉搜索树(BST)的根节点 root ,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。

如果树中有不止一个众数,可以按 任意顺序 返回。

假定 BST 满足如下定义:

  • 结点左子树中所含节点的值 小于等于 当前节点的值
  • 结点右子树中所含节点的值 大于等于 当前节点的值
  • 左子树和右子树都是二叉搜索树

思路:

大思路仍然依靠中序遍历二叉搜索树相当于遍历有序数组,问题转换为求出一个有序数组中的众数,那么在遍历时记录每个数的频率,维护一个最大频率

若该数最后的频率小于最大频率,则不做操作;等于最大频率,则加入答案中;大于最大频率,则更新最大频率,清空当前答案,并将当前数加入答案

依然是递归中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
vector<int> ans;//答案answer
int max_freq = 0;//最大频率
void dfs(TreeNode * root, int &cur, int &freq) {
if(root == nullptr) return;
dfs(root->left, cur, freq);//中序左
if(root->val == cur) {//当前数cur还未遍历完,继续加频率freq
freq++;
if(max_freq == freq) {//如果已经赶上最大频率,加入答案
ans.push_back(cur);
}
else if(max_freq < freq) {//如果已经超过,更新max,清空答案,重新加入cur作为答案
max_freq = freq;
ans.clear();
ans.push_back(cur);
}
}
else{
cur = root->val;//当前数cur遍历结束,将cur更新为新的数,频率重置
freq = 1;
}
dfs(root->right, cur, freq);
}
vector<int> findMode(TreeNode* root) {
int cur = root->val, freq = 0;
dfs(root, cur, freq);
return ans;
}
};

236. 二叉搜索树的最近公共祖先

题目:

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”

思路

初次尝试越想越复杂,以失败告终,原因是单次递归逻辑和终止条件没想明白,

按照carl的递归三部曲:

  1. 确定递归返回值和参数。这一步没问题,就按照力扣给的核心方法的定义就可以,返回公共祖先的指针,参数就是两个节点p、q和根节点
  2. 确定递归终止条件。第一个终止条件想到了:“root等于p或者q时,或者root为空”就返回root。之后就开始混乱了,尝试讨论p、q是root的孩子还是孙子还是更远的孩子,遂失败
  3. 确定单次递归逻辑。失败

我没有分析出:当递归到 最近公共祖先的祖先时,返回值也应该是最近公共祖先,也就是说最近公共祖先是会不断向上传递的,这样就就能保证最近而不会得到深度更浅的公共祖先。

对于遍历一条路还是遍历整棵树,carl老师的解释令我耳目一新:

在递归函数有返回值的情况下:如果要搜索一条边,递归函数返回值不为空的时候,立刻返回,如果搜索整个树,直接用一个变量left、right接住返回值,这个left、right后序还有逻辑处理的需要,也就是后序遍历中处理中间节点的逻辑(也是回溯)。

搜索一条边的写法:

1
2
if (递归函数(root->left)) return ;
if (递归函数(root->right)) return ;
搜索整个树写法:
1
2
3
left = 递归函数(root->left);  // 左
right = 递归函数(root->right); // 右
leftright的逻辑处理; // 中

由于返回值确定,所以递归时肯定会有东西接住返回值,又由于,递归的参数是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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
if(root == p || root == q || root == nullptr) return root;

TreeNode * left = lowestCommonAncestor(root->left, p, q);
TreeNode * right = lowestCommonAncestor(root->right, p, q);

if(left == nullptr && right == nullptr)
return nullptr;
else if(left == nullptr && right != nullptr)
return right;
else if(left != nullptr && right == nullptr)
return left;
else
return root;
}
};

对于想了半小时还WA的我来说,这真是段优雅的代码


leetcode_day21
https://novelyear.github.io/2024/06/13/leetcode-day21/
作者
Leoo Yann
更新于
2024年6月13日
许可协议