当前位置：首页 > news >正文

24暑假算法刷题 | Day18 | LeetCode 530. 二叉搜索树的最小绝对差，501. 二叉搜索树中的众数，236. 二叉树的最近公共祖先

news 来源：原创 2024/9/20 9:36:38

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)$ 。

我们可以利用二叉搜索树的一个重要性质来优化算法：

二叉搜索树的中序遍历结果是一个从小到大的有序数列

此处默认节点左子树中各节点值小于节点、右子树中各节点值大于节点，则上面的性质是显然的。

也就是说，如果我们先获得中序遍历结果，再从头到尾依次两两相减，只需要遍历一次就可以得出最小绝对差。

由于中序遍历结果是递增序列，最小的任意两数之差肯定出现在相邻的两数之间；且后一个数大于前一个数，所以总让后一个数减去前一个数，所得结果必为正数，不必再求绝对值。

显然，这一算法可以直接在中序遍历的过程中运行，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++; // 相同的节点值elsecurShowTime = 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;
}