530. 二叉搜索树的最小绝对差
题目描述
给你一个二叉搜索树的根节点 root
,返回 树中任意两不同节点值之间的最小差值 。
差值是一个正数,其数值等于两值之差的绝对值。
示例 1:
输入:root = [4,2,6,1,3]
输出:1
示例 2:
输入:root = [1,0,48,null,null,12,49]
输出:1
提示:
- 树中节点的数目范围是
[2, 104]
0 <= Node.val <= 105
题解
暴力解法把所有节点两两相减、求绝对值最小的差即可,时间复杂度为 O ( n 2 ) O(n^2) O(n2) 。
我们可以利用二叉搜索树的一个重要性质来优化算法:
- 二叉搜索树的中序遍历结果是一个从小到大的有序数列
此处默认节点左子树中各节点值小于节点、右子树中各节点值大于节点,则上面的性质是显然的。
也就是说,如果我们先获得中序遍历结果,再从头到尾依次两两相减,只需要遍历一次就可以得出最小绝对差。
由于中序遍历结果是递增序列,最小的任意两数之差肯定出现在相邻的两数之间;且后一个数大于前一个数,所以总让后一个数减去前一个数,所得结果必为正数,不必再求绝对值。
显然,这一算法可以直接在中序遍历的过程中运行,C++代码如下:
int res = INT_MAX;
TreeNode *pre; // 暂存中序遍历时前一个节点的指针
void traversal(TreeNode *root)
{
if (root->left)
traversal(root->left); // 左
if (pre)
res = min(res, root->val - pre->val); // 中
pre = root; // 更新前指针
if (root->right)
traversal(root->right); // 右
}
int getMinimumDifference(TreeNode *root)
{
traversal(root);
return res;
}
501. 二叉搜索树中的众数
题目描述
给你一个含重复值的二叉搜索树(BST)的根节点 root
,找出并返回 BST 中的所有 众数(即,出现频率最高的元素)。
如果树中有不止一个众数,可以按 任意顺序 返回。
假定 BST 满足如下定义:
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1:
输入:root = [1,null,2,2]
输出:[2]
示例 2:
输入:root = [0]
输出:[0]
提示:
- 树中节点的数目在范围
[1, 104]
内 -105 <= Node.val <= 105
进阶: 你可以不使用额外的空间吗?(假设由递归产生的隐式调用栈的开销不被计算在内)
题解
既然是找众数,那么将二叉树遍历一遍、记录每个数出现的频率,是必不可少的了。常规思路应该是:
遍历该树,同时记录节点值的出现频率
找到最大的出现频率
将出现频率最大的数加入结果集
⚠️ 注意题目说了,众数可能不止一个
当然,后两步可以合并:当发现更大的频率的时候,先将现有结果集清空,再加入新的最高频数字。这种方法的C++代码如下:
class Solution
{
public:
unordered_map<int, int> freqMap; // 用一个哈希表记录每个数值出现的频率
int maxShowTime = -1;
// 中序遍历
void traversal(TreeNode *cur)
{
if (cur->left)
traversal(cur->left); // 左
freqMap[cur->val]++; // 中
if (cur->right)
traversal(cur->right); // 右
}
vector<int> findMode(TreeNode *root)
{
traversal(root);
vector<int> res;
for (const auto &pair : freqMap)
{
if (pair.second > maxShowTime)
{
maxShowTime = pair.second;
res.clear(); // 出现更高频的元素,将原来的结果集清空
res.push_back(pair.first);
}
else if (pair.second == maxShowTime)
res.push_back(pair.first); // 众数可能不止一个
}
return res;
}
};
不过,上述方法显然对任意树是通用的,意味着我们并没有利用到二叉搜索树的独特性质。同时,题目进阶要求也说了,可以不使用额外空间解决此题(上面的算法有个额外的哈希表空间开销)。
即是二叉搜索树,又要遍历之,自然联想到性质:
- 二叉搜索树的中序遍历结果是一个从小到大的有序数列
所以,我们可以采用中序遍历的方法:
- 如果当前节点值和上一个节点值相同,则当前频率加1;否则,说明遍历到一个新数值的节点,将当前频率重置为1
- 如果当前频率等于最大频率,则将当前节点值加入结果集
- 如果当前频率大于最大频率,则更新最大频率,清空原来结果集,将当前节点值接入结果集
这样,就避免了额外的空间开销:
class Solution
{
public:
int maxShowTime = -1;
int curShowTime = 0;
TreeNode *pre = nullptr; // 中序遍历序列中,当前节点的前一个节点
vector<int> res;
// 中序遍历
void traversal(TreeNode *cur)
{
// 左
if (cur->left)
traversal(cur->left);
// 中
if (!pre)
curShowTime = 1; // 第一个节点
else if (cur->val == pre->val)
curShowTime++; // 相同的节点值
else
curShowTime = 1; // 新的节点值
pre = cur; // 更新前节点指针
if (curShowTime == maxShowTime)
res.push_back(cur->val);
if (curShowTime > maxShowTime) {
maxShowTime = curShowTime; // 更新最大出现频率
res.clear(); // 清除之前的结果
res.push_back(cur->val);
}
// 右
if (cur->right)
traversal(cur->right);
}
vector<int> findMode(TreeNode *root)
{
traversal(root);
return res;
}
};
236. 二叉树的最近公共祖先
题目描述
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
示例 1:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出:3
解释:节点 5 和节点 1 的最近公共祖先是节点 3 。
示例 2:
输入:root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出:5
解释:节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。
示例 3:
输入:root = [1,2], p = 1, q = 2
输出:1
提示:
- 树中节点数目在范围
[2, 105]
内。 -109 <= Node.val <= 109
- 所有
Node.val
互不相同
。 p != q
p
和q
均存在于给定的二叉树中。
题解
根据题目描述,可以发现,符合直觉的思路是自底向上地查找——而这与后序遍历的遍历顺序相符。所以,我们考虑基于后序遍历,递归地返回 p
和 q
的最近公共祖先。
用递归,首先考虑递归出口。我们想要返回的总是一个 p
和/或 q
的祖宗节点,所以以当前节点 root
的左右子树中必须有 p
和/或 q
(自然,也有其祖宗节点),否则返回空节点:
if (!left && !right)
return nullptr;
按照这种思路,节点不为空即说明该节点是
p
或q
或者它们之一/公共的祖宗节点
其余情况,即 root
的左右子树不都为空,说明它们之中有 p
和/或 q
及其祖宗节点:
1️⃣ 先看看最简单的情况:类似上面的示例1,当前节点 root
的左孩子 left
和 right
恰好就是 p
和 q
(对应关系无所谓),则 root
就是它们的最近公共祖先,此时返回 root
即可:
if (left && right)
return root;
2️⃣ 如果当前节点是 p
或 q
,也直接返回当前节点即可:题目说了 一个节点也可以是它自己的祖先
if (root == p || root == q)
return root;
3️⃣ 如果 left
和 right
之间有且仅有一个不为空,则返回不为空的那个节点——该节点是 p
或 q
或它们之一/公共的祖先:
相当于上面示例2中的节点
2
if (left && !right)
return left;
if (!left && right)
return right;
整体C++代码如下:
TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
{
// 基于后序遍历
if (!root)
return nullptr;
TreeNode *left = lowestCommonAncestor(root->left, p, q); // 左
TreeNode *right = lowestCommonAncestor(root->right, p, q); // 右
// 中
// 当前节点为p, q之一
if (root == p || root == q)
return root;
// 否则,看左右孩子节点的情况
else if (left && right)
return root;
else if (left && !right)
return left;
else if (!left && right)
return right;
else // 左右都为空
return nullptr;
}
该算法更详细的讲解参见 代码随想录的本题题解 。