算法训练营day20 | {530.二叉搜索树的最小绝对差, 501.二叉搜索树中的众数, 236.二叉树的最近公共祖先}

第六章二叉树part06，二叉搜索树经过中序遍历之后是一个有序的递增序列，要利用好这一点。

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

1.1 解题分析

  • 本题是一个二叉搜索树，遇到在BST上求最值、差值之类的问题，把它想成一个有序数组上求最值、求差值，这样就简单多了。
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    int result = Integer.MAX_VALUE;
    TreeNode pre = null;
    
    public int getMinimumDifference(TreeNode root) {
        if(root == null) return result;
        result = Math.min(result, getMinimumDifference(root.left));
        if (pre != null) result = Math.min(result, root.val- pre.val);
        pre = root;
        return Math.min(result, getMinimumDifference(root.right));
    }
}

501. 二叉搜索树中的众数

2.1 解题分析

  • 分析递归三步曲：

    1. 参数和返回值是什么？ 要传入一个根节点，全局变量需要定义一个count记录出现次数，初始为0，一个最大出现次数maxCount，一个pre指针记录开始计数的位置；不需要返回值。
    2. 确定递归的终止条件。 如果当前遍历到空节点了，就返回。
    3. 确定单层递归的逻辑。 中序遍历，左中右，保证是一个非递减的遍历，注意当maxCount迎来更新时，要把目前暂存的“众数”结果全部弹出，再进行存入。

  • 注意这边就用到了昨天总结的关于递归函数什么时候需要定义全局变量？什么时候不需要？

    1. 当需要左右子树共享信息时，需要定义全局变量；
    2. 当每次递归是一个个独立的子问题时，不需要全局变量。

  • 再次强调形参的语义：形参=父问题给子问题的约束。

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
31
32
class Solution {
    int maxCount = 0;
    int count = 0;
    TreeNode pre = null;
    List<TreeNode> ans = new ArrayList<>();

    public int[] findMode(TreeNode root) {
        getMode(root);
        int[] result = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            result[i] = ans.get(i).val;
        }
        return result;
    }

    public void getMode(TreeNode node) {
        if (node == null) return;
        getMode(node.left);
        if (pre == null) count = 1;
        else if (pre.val == node.val) count++;
        else count = 1;
        pre = node;
        if (count >= maxCount) {
            if (count > maxCount) {
                while (!ans.isEmpty()) ans.removeLast();
            }
            ans.add(node);
            maxCount = count;
        }
        getMode(node.right);
    }
}

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

3.1 解题分析

  • 审题，本题的二叉树中，所有节点的值均不相同，所以节点p或q的值不可能在树中出现两次。

  • 分析递归三步曲：

    1. 参数和返回值是什么？ 要传入一个根节点，指定的节点p、节点q；返回值是TreeNode
    2. 确定递归的终止条件。 如果当前遍历到空节点，则返回null；如果当前遍历到q节点或p节点，则直接返回该节点。
    3. 确定单层递归的逻辑。 后序遍历，左右中，情况1，如果左子树和右子树返回的结果均不为空，那么当前节点就是最近的公共祖先；情况2，如果左子树或右子树其中一个为空，另一个不为空，继续向上返回不为空的结果，此种情况最好结合画图理解。
      情况2示例图
1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) return root;
        TreeNode leftRes = lowestCommonAncestor(root.left, p, q);
        TreeNode rightRes = lowestCommonAncestor(root.right, p, q);
        if (leftRes != null && rightRes != null) return root;
        else if (leftRes == null && rightRes != null) return rightRes;
        else if (leftRes != null && rightRes == null) return leftRes;
        else return null;
    }
}

5. 今日收获

  • 对于一个二叉搜索树，第一时间要想到它中序遍历之后是一个递增的有序序列的特性。接着将求最值、求差值问题，自然地转化为一个有序数组中求最值/差值的问题。
  • 继续巩固了关于递归函数什么时候需要定义全局变量？什么时候不需要的问题，能够掌握了。
  • 学习时长：2.5小时
Leetcode > 二叉搜索树
#Java #代码随想录
算法训练营day20 | {530.二叉搜索树的最小绝对差, 501.二叉搜索树中的众数, 236.二叉树的最近公共祖先}
http://paopaotangzu.xyz/cn/day20_leetcode/
作者
PROTON TANG
发布于
2026年1月5日
许可协议