如何找到二叉搜索树中的众数？

简化版

BST 中序遍历会得到有序序列，相同值会连续出现。遍历时维护当前值、当前连续次数、历史最大次数和答案列表，就能 O(n) 找到所有众数。

详细版

如果不利用 BST 性质，可以用 HashMap 统计每个值出现次数，时间 O(n)、空间 O(n)。但 BST 的中序序列有序，相同值连续，所以可以只用几个变量在线统计：

prev：上一个访问的节点值；
count：当前值连续出现次数；
maxCount：目前发现的最大次数；
modes：所有出现次数等于 maxCount 的值。

每访问一个值：

若等于 prev，count++；
否则切换到新值，count=1；
若 count > maxCount，清空答案并加入当前值；
若 count == maxCount，追加当前值。

时间复杂度 O(n)，递归栈空间 O(h)，答案空间不计时额外空间接近 O(h)。

完整版教学

一、众数问题和 BST 有什么关系

众数是出现次数最多的值。普通二叉树里，相同值可能分散在任意位置，所以通常要 HashMap 统计全局频次。BST 不同：它的中序遍历是非降序序列，所有相同值会被挤在一起，像排序数组一样连续出现。于是问题就从「统计任意散落的频次」变成「统计连续段长度」。

举个例子，BST 中序结果是 [1,2,2,2,3,4,4]。值 2 连续 3 次，值 4 连续 2 次，所以众数是 2。我们不需要记住每个值的次数，只要在遍历过程中记录当前连续段长度即可。

记忆钩子：BST 的中序序列像一排排好队的人，相同值站在一起；找众数就是找最长的那一段队伍。

二、为什么相同值会连续出现

BST 的定义通常是左子树值不大于根，右子树值不小于根，或者更严格地左小右大。无论采用哪种重复值放置策略，只要它仍保证中序遍历非降序，相同值在中序序列里就不会被更大或更小的值隔开。因为一旦出现 x ... y ... x 且 y != x，非降序顺序就会被破坏。

这个性质非常关键。它让我们可以用 prev 和 count 模拟排序数组的游程统计：

中序序列: 1 2 2 2 3 4 4
连续段:   [1] [2 2 2] [3] [4 4]
频次:      1      3     1    2

如果不是 BST，DFS 顺序可能是 [2,1,2,4,2]，相同值不连续，单靠 prev/count 就会算错。

三、一次遍历如何维护答案

核心变量有 4 个：prevVal、count、maxCount、ans。访问一个新值 x 时，先判断它是否和上一个值相同。如果相同，连续段长度加 1；如果不同，开启新连续段，长度回到 1。然后拿当前 count 和 maxCount 比较。

Integer prev = null;
int count = 0, maxCount = 0;
List<Integer> ans = new ArrayList<>();

void handle(int x) {
    if (prev != null && prev == x) count++;
    else count = 1;
    prev = x;

    if (count > maxCount) {
        maxCount = count;
        ans.clear();
        ans.add(x);
    } else if (count == maxCount) {
        ans.add(x);
    }
}

注意 prev 用 Integer 是为了表达「还没有上一个值」。如果节点值范围很宽，不建议用某个哨兵值假装空值。

四、完整代码和执行顺序

把 handle 嵌入中序遍历即可。中序访问顺序必须是左、根、右；如果写成前序或后序，相同值不一定连续，统计就失效。

List<Integer> findMode(TreeNode root) {
    inorder(root);
    return ans;
}

void inorder(TreeNode node) {
    if (node == null) return;
    inorder(node.left);
    handle(node.val);
    inorder(node.right);
}

执行过程可以用一个小表看清楚：

访问值	count	maxCount	ans
1	1	1	[1]
2	1	1	[1,2]
2	2	2	[2]
3	1	2	[2]
3	2	2	[2,3]

当出现新的更大频次时要清空旧答案，因为旧答案已经不是众数；当频次追平时要追加，因为众数可能有多个。

五、空间复杂度为什么常说接近 O(h)

如果不算输出答案，算法只维护几个变量，递归调用栈是 O(h)，h 是树高。平衡 BST 中 h≈log n，退化 BST 中 h≈n。如果题目要求严格 O(1) 额外空间，可以用 Morris 中序遍历消除递归栈，但代码复杂度会上升。

很多题解会说「不用额外空间」，这通常默认不计算递归栈或输出数组。面试时最好说严谨一点：递归版额外空间 O(h)，Morris 版可做到 O(1) 额外空间但会临时改动树指针再恢复。

六、和 HashMap 统计相比有什么取舍

HashMap 统计更通用，不要求树有序。它遍历每个节点，把值映射到次数，最后扫描 Map 找最大频次。缺点是空间 O(k)，k 是不同值个数，最坏 O(n)。

方法	利用 BST	时间	额外空间	实现风险
HashMap 统计	否	O(n)	O(n)	低
中序连续计数	是	O(n)	O(h)	中
Morris 中序	是	O(n)	O(1)	高

如果题目明确是 BST，应优先讲中序连续计数；如果题目只是普通二叉树，HashMap 才是稳妥答案。

七、常见误区与追问

误区：BST 众数可以直接看根节点。 根的位置不代表频次，众数必须基于全树统计。
追问：为什么中序能让相同值连续？ 因为中序结果非降序，相同值之间不可能夹着不同大小的值。
误区：count == maxCount 时不需要追加答案。 众数可能有多个，追平最大频次也要记录。
追问：如果树不允许重复值怎么办？ 每个值次数都是 1，所有节点都是众数，算法仍然成立。
误区：递归版一定是 O(1) 空间。 递归调用栈是 O(h)，除非改成 Morris 遍历并恢复指针。

八、加强记忆

这题的核心不是「众数」两个字，而是 BST 中序的排序效果。排序后，相同值自然连续，统计频次就变成统计连续段长度。牢记 4 个变量：上一个值、当前连续次数、最大次数、答案列表。新的最大次数出现时清空答案，追平最大次数时追加答案；这样才能正确处理多个众数。

简化版

详细版