LeetCode 501. 二叉搜索树中的众数

2022-07-16 HGNULB 约 10 分钟

文章信息 6 个分类 4 个标签

分类

题目描述

✅ 501. 二叉搜索树中的众数

题意分析

给定一棵允许出现重复值的二叉搜索树，要求返回所有出现次数最多的值。众数可能不止一个，此时全部返回，顺序不限。这里的 BST 定义放宽了：左子树的值小于等于根，右子树的值大于等于根，正因为允许相等，重复值才可能同时挂在左右两侧。

题面里给的进阶条件是解题的关键信号：「不使用额外的空间（递归产生的隐式调用栈不算）」。这句话直接否掉了「开一个哈希表统计每个值出现多少次，再挑最大的」这条最自然的路。既然不给哈希表，就必须依赖输入本身的结构性质——而 BST 唯一的结构红利就是它的有序性。

边界上要考虑：树为空（返回空数组）；只有一个节点（它自己就是唯一众数，出现 $1$ 次）；所有节点值都不相同（每个值都出现 $1$ 次，全部都是众数，答案长度等于节点数）；所有节点值完全相同（答案只有一个元素）。节点数上限是 $10^4$，量级很小，任何线性做法都绰绰有余，所以这题考的完全不是效率，而是能不能想到用有序性替代哈希表。

解法：中序遍历统计频次

核心思路

暴力解法是遍历整棵树，把每个值往 HashMap<Integer, Integer> 里累加，遍历结束后扫一遍哈希表找最大计数，再扫一遍收集所有达到最大计数的键。这是 $O(n)$ 时间 $O(n)$ 空间，能过，但它把 BST 当成了一棵普通二叉树，完全浪费了题目给的结构，也违背了进阶要求。

瓶颈在于「统计每个值的出现次数」这件事本身需要随机访问——因为相同的值可能散落在树的任意角落。观察 BST 的中序遍历：它输出的是一个非递减序列。既然序列有序，所有相同的值就必然连续排列在一起。那么统计频次就从「随机访问的计数问题」退化成了「有序数组里数连续段长度」，而后者只需要记住上一个元素是什么，不需要任何表。

于是维护的不变量是：在中序遍历访问到某个节点的瞬间，prev 是中序序列里它的前驱值，count 是包含当前节点在内、以当前值结尾的连续相同段的长度，maxCount 是已经扫过的所有连续段中的最大长度，modes 恰好是这些已扫段中长度等于 maxCount 的那些值的集合。三者在每个节点上按固定顺序更新，遍历结束时不变量作用于整个序列，modes 就是最终答案。

更新 count 的规则很短：当前值等于 prev 就 count++，否则 count = 1 并刷新 prev。更新答案的规则是经典的「打擂台 + 并列收集」三分支：count > maxCount 说明找到了更强的段，清空 modes 重新收集；count == maxCount 说明并列，追加进去；count < maxCount 什么都不做。用 Integer prev = null（Go 里用 hasPrev 布尔标志）而不是 int prev = 0 作为初值，是为了区分「还没有前驱」和「前驱恰好是 $0$」这两种情形，因为节点值允许为负也允许为 $0$。

解题步骤

声明四个跨递归层共享的状态：prev（上一个中序值，初始为「不存在」）、count（当前连续段长度）、maxCount（历史最大段长）、modes（结果收集列表）。理由：中序遍历的相邻关系跨越了递归的父子边界——一个节点的中序前驱可能在它左子树的最右下角，靠递归返回值传不方便，用共享状态最直白。

写标准中序递归：先 inorder(node.left)，再处理当前节点，最后 inorder(node.right)。理由：这个顺序是「有序性」的来源，一旦写成前序或后序，序列不再有序，相同值不再连续，整套推理就崩了。

空节点直接 return。理由：递归的出口，同时也保证叶子节点的左右孩子调用能安全返回，不需要在父层判空。

处理当前节点第一步：若 prev 不存在或 node.val != prev，令 count = 1 并把 prev 更新为 node.val；否则 count++。理由：count 的语义是「以当前值结尾的连续段长度」，遇到新值必须重新起算而不是继续累加。

处理当前节点第二步：若 count > maxCount，则 maxCount = count、modes.clear()、modes.add(node.val)；否则若 count == maxCount，则 modes.add(node.val)。理由：clear 是必须的，否则之前那些计数更小的候选会残留在答案里；两个分支必须是 else if，写成两个独立 if 会在刷新 maxCount 后立刻又满足相等条件，把同一个值加两遍。

注意一个容易被忽略的细节：同一个值在它的连续段里会被多次加入 modes，但每次加入前 count 都在增长，只有 count == maxCount 那一刻的加入会保留下来，更早的加入要么因为 count < maxCount 根本没发生，要么在后续 count > maxCount 时被 clear 掉了。理由：这是这套写法自洽的关键，理解了它就不会画蛇添足地去做去重。

递归返回后把 modes 转成 int[]（Go 直接返回切片）。理由：题目签名要求返回数组。

以下面这棵树走一遍：根为 1，右孩子为 2，2 的左孩子为 2（即 [1, null, 2, 2]）。中序序列是 1, 2, 2。访问 1：prev 不存在，count = 1，prev = 1；count(1) > maxCount(0)，于是 maxCount = 1，modes 清空后变成 [1]。访问第一个 2（是右子树里最左的那个）：2 != prev(1)，count = 1，prev = 2；count(1) == maxCount(1)，追加，modes = [1, 2]。访问第二个 2（右子树的根）：2 == prev(2)，count = 2；count(2) > maxCount(1)，于是 maxCount = 2，modes 清空并变成 [2]。遍历结束，返回 [2]。可以看到 clear 这一步正确地把只出现一次的 1 和早先并列的 2 一起清掉了，最终只留下真正的众数。

代码实现

class Solution {
    private Integer prev = null;
    private int count = 0;
    private int maxCount = 0;
    private final List<Integer> modes = new ArrayList<>();

    public int[] findMode(TreeNode root) {
        inorder(root);

        int[] res = new int[modes.size()];
        for (int i = 0; i < modes.size(); i++) {
            res[i] = modes.get(i);
        }
        return res;
    }

    private void inorder(TreeNode node) {
        if (node == null) {
            return;
        }

        inorder(node.left);

        if (prev == null || node.val != prev) {
            count = 1;
            prev = node.val;
        } else {
            count++;
        }

        if (count > maxCount) {
            maxCount = count;
            modes.clear();
            modes.add(node.val);
        } else if (count == maxCount) {
            modes.add(node.val);
        }

        inorder(node.right);
    }
}

func findMode(root *TreeNode) []int {
    hasPrev := false
    prevVal := 0
    count := 0
    maxCount := 0
    modes := make([]int, 0)

    var inorder func(node *TreeNode)
    inorder = func(node *TreeNode) {
        if node == nil {
            return
        }

        inorder(node.Left)

        if !hasPrev || node.Val != prevVal {
            count = 1
            prevVal = node.Val
            hasPrev = true
        } else {
            count++
        }

        if count > maxCount {
            maxCount = count
            modes = modes[:0]
            modes = append(modes, node.Val)
        } else if count == maxCount {
            modes = append(modes, node.Val)
        }

        inorder(node.Right)
    }

    inorder(root)
    return modes
}

复杂度分析

时间复杂度：$O(n)$，其中 $n$ 是二叉树的节点数。中序遍历对每个节点恰好访问一次，每次访问内部只做常数次比较和一次列表追加；modes.clear() 看似昂贵，但每个元素最多被加入一次、被清除一次，均摊下来仍是 $O(1)$，总量不超过 $O(n)$。

空间复杂度：$O(h)$ 的递归栈，其中 $h$ 是树高，平衡时是 $O(\log n)$，退化成链时是 $O(n)$；除此之外只用了 prev、count、maxCount 三个标量，是常数额外空间，符合进阶要求。返回值 modes 最坏为 $O(n)$（所有值互不相同时全都是众数），但它是答案本身，通常不计入额外空间。

关键点总结

看到 BST 就要立刻条件反射「中序 = 有序」。BST 类题目里超过一半的解法都是把问题先翻译成「有序数组上的问题」，再套有序数组的技巧：本题是数连续段，530 是求相邻差，230 是取第 k 个，98 是验证严格递增。

「不用额外空间统计频次」的通解是把随机访问需求转化为相邻访问需求。只要能保证相同元素连续出现，一个 prev 变量就能顶替整张哈希表——这个思路在排序数组去重、游程编码、日志按时间聚合里完全一致。

「打擂台同时收集并列冠军」的三分支模板要背熟：> 时清空重收，== 时追加，< 时忽略。写成两个平行 if 是最常见的翻车点，一定要用 else if 串起来。

用「哨兵不存在」而不是「哨兵取某个魔法值」来表示初始状态。本题值域含负数和 $0$，prev = Integer.MIN_VALUE 在极端用例下会误判成「与前驱相同」；Java 用包装类型 null、Go 用额外布尔标志，才是可靠写法。

面试视角：字节跳动考这题时，暴力哈希表版本只能拿到基础分，面试官真正想听的是你主动说出「因为是 BST，中序有序，相同值连续，所以一个 prev 就够了」。答完主解法后，如果还能补一句「递归栈可以用 Morris 遍历消掉，做到真正的 $O(1)$ 空间」，就是加分项——但不必真写，Morris 不是白板友好的代码。

易错点总结

错误写法：把更新答案的两个分支写成两个独立的 if（if (count > maxCount) {...} 后面紧跟 if (count == maxCount) {...}）→ 用例 [1] → 第一个 if 把 maxCount 改成 $1$ 并加入 1，第二个 if 此时 count == maxCount 也成立，再加一次，返回 [1, 1] 而不是 [1]。

错误写法：count > maxCount 分支里忘记 modes.clear() → 用例 [1, null, 2, 2] → 只出现一次的 1 残留在结果里，返回 [1, 2, 2] 而不是 [2]。

错误写法：用 int prev = Integer.MIN_VALUE 当哨兵 → 用例 [-2147483648]（单节点，值恰为 Integer.MIN_VALUE）→ 第一个节点就被判成「与前驱相同」，count 从 $0$ 加到 $1$ 看似侥幸正确，但换成 [-2147483648, -2147483648] 这类树时段长统计整体偏移，众数判定出错。

错误写法：把中序写成前序（先处理当前节点再递归左右）→ 用例 [2, 1, 2]（根 2，左 1，右 2）→ 访问序列变成 2, 1, 2，两个 2 不再相邻，count 一直是 $1$，返回 [2, 1, 2] 而正确答案是 [2]。

错误写法：count 在遇到新值时写成 count = 0 而不是 count = 1 → 用例 [1, null, 2] → 访问 2 时 count 归零后没有自增，count(0) 既不大于也不等于 maxCount(1)，2 被漏掉，返回 [1] 而正确答案是 [1, 2]。

错误写法：Go 里清空切片用 modes = nil 之后又依赖它的容量，或者用 modes = modes[:0] 却在别处保存了旧切片的引用 → 用例 [1, null, 2, 2] → 旧引用与新写入共享底层数组，[1] 被原地改写成 [2] 后又被追加，输出出现重复元素。

错误写法：先把中序序列收进一个 List<Integer> 再统计 → 用例 $10^4$ 个节点的树 → 结果正确但额外空间是 $O(n)$，直接违背进阶要求「不使用额外空间」，面试中会被要求重写。

错误写法：更新 prev 的位置放在整个节点处理逻辑之后（即先比较、再更新答案、最后才 prev = node.val），但比较分支里遗漏了「值相同时也要保持 prev 不变」的一致性，写成每次都 prev = node.val 却把 count 的判断放在赋值之后 → 用例 [2, 2, 2] → prev 永远等于当前值，node.val != prev 恒不成立或恒成立，count 要么永远是 $1$ 要么无限累加，众数判定完全失效。

错误写法：认为「BST 中序有序所以众数一定只有一个」，找到 maxCount 后直接返回单元素数组 → 用例 [1, null, 2] → 1 和 2 各出现一次并列，正确答案是 [1, 2]，只返回其中一个会判错。

错误写法：递归函数里把 count、maxCount 声明成局部变量而非共享状态 → 用例任意含重复值的树 → 每层递归各自持有一份计数，父层看不到子树的统计结果，maxCount 恒为 $1$，返回全部节点值。

相似题目

题目	难度	考察点
530. 二叉搜索树的最小绝对差	简单	同样用 `prev` 记录中序前驱，但求的是相邻差的最小值而非连续段长度
230. 二叉搜索树中第 K 小的元素	中等	中序过程中做计数并提前剪枝返回，不需要走完整棵树
98. 验证二叉搜索树	中等	用中序前驱做严格递增校验，与本题「允许相等」的定义正好相反
173. 二叉搜索树迭代器	中等	把中序遍历拆成可暂停的迭代器，需要显式栈而不能用递归
538. 把二叉搜索树转换为累加树	中等	走反中序（右-根-左）并累加后缀和，考察遍历方向的灵活变换