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

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++; // 相同的节点值
        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;
}

该算法更详细的讲解参见 代码随想录的本题题解 。