LeetCode 501. 二叉搜索树中的众数
题目描述
题意分析
返回二叉搜索树中出现次数最多的全部值。这棵树允许重复值：左子树的值不大于根，右子树的值不小于根，因此中序遍历得到非递减序列，相同值必然连续出现，可以用连续段长度统计频次。
进阶要求不使用额外空间，并明确不计递归调用栈。普通单趟遍历会保留中途的候选列表；第二种方法用两趟遍历，只分配最终答案需要的空间。
解法：中序遍历统计频次
核心思路
[!blue]
按左、根、右访问，维护
prev、count、maxCount：分别表示上一个中序值、当前相同值连续段的长度，以及已访问部分的最高频次。遇到相同值就延长当前段，遇到新值则将count重置为1。若
count > maxCount，当前值建立了新的最高频次，旧候选全部失效，清空后只保留当前值；若count == maxCount，当前值与已有候选并列，追加它；较小时不改答案。这样每次访问后，候选都恰好是已访问部分的众数。同一段不会留下重复候选：计数第一次追平历史最高值时可能追加一次，若继续增长，就会超过最高值并清空列表、重新保留当前值。遍历结束时，相同值的整段都已处理，候选就是整棵树的全部众数。
解题步骤
- 开始一次查询时重置统计。
- 按左、根、右访问，相同值延长计数，新值从一开始。
- 更大次数清空重收，相同次数追加。
- 返回全部候选值。
第一个节点没有前驱，不能用某个合法整数值充当前驱哨兵。Java 用
null、Go 用hasPrev区分；Java 成员字段还要在每次入口重置，防止复用对象时混入上次结果。
代码实现
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) {
// 每次入口重置全部统计，空树调用也不能继承旧结果
prev = null;
count = 0;
maxCount = 0;
modes.clear();
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)$，每个节点处理一次，候选的追加与清除总量线性。
- 空间复杂度：$O(n+h)$，递归栈为 h，候选缓冲峰值可为 n，即使最终众数只有一个。
关键点总结
[!green]
- 前驱是中序前驱，不一定是父节点。
- 候选缓冲在途中可能比最终结果更大。
解法二：两趟中序遍历（进阶）
核心思路
[!blue]
单趟方法可能先收集许多低频候选，后来又全部清除，即使最终答案很短，候选缓冲峰值仍可能是
O(n)。要满足进阶，可以先只统计最高频次maxCount和达到该频次的不同值数量modeCount，不保存候选值。第一趟仍按连续段计数：出现更高频次时，把
modeCount置为1；追平已有最高频次时，将它加一。若当前段继续增长，下一次建立新高又会重置数量，所以第一趟结束时得到的正好是全局最高频次和最终众数个数。然后创建长度恰好为
modeCount的结果数组，重置前驱与连续计数，再中序遍历一遍。这次maxCount已经固定，每当某段的计数达到它，就写入该值；非众数达不到这个次数，每个众数也只会达到一次，因此结果不漏不重。代码用答案数组尚未分配来区分第一趟与第二趟，使两趟共享同一套遍历和连续段更新逻辑。除最终结果与题目不计的递归栈外，只保存常数个统计状态。
解题步骤
- 重置全部状态，第一趟中序遍历计算
maxCount与modeCount。- 分配长度为
modeCount的答案数组，重置前驱和连续计数。- 第二趟中序遍历，每当连续次数达到
maxCount，顺序写入当前值。- 返回填满的答案数组。
代码实现
class Solution {
private Integer prev;
private int count;
private int maxCount;
private int modeCount;
private int index;
private int[] answer;
public int[] findMode(TreeNode root) {
prev = null;
count = 0;
maxCount = 0;
modeCount = 0;
index = 0;
answer = null;
inorder(root);
answer = new int[modeCount];
prev = null;
count = 0;
inorder(root);
return answer;
}
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 (answer == null) {
if (count > maxCount) {
maxCount = count;
modeCount = 1;
} else if (count == maxCount) {
modeCount++;
}
} else if (count == maxCount) {
answer[index++] = node.val;
}
inorder(node.right);
}
}
func findMode(root *TreeNode) []int {
hasPrev := false
prev, count, maxCount, modeCount, index := 0, 0, 0, 0, 0
var answer []int
var inorder func(*TreeNode)
inorder = func(node *TreeNode) {
if node == nil {
return
}
inorder(node.Left)
if !hasPrev || node.Val != prev {
count = 1
prev = node.Val
hasPrev = true
} else {
count++
}
if answer == nil {
if count > maxCount {
maxCount = count
modeCount = 1
} else if count == maxCount {
modeCount++
}
} else if count == maxCount {
answer[index] = node.Val
index++
}
inorder(node.Right)
}
inorder(root)
answer = make([]int, modeCount)
hasPrev = false
count = 0
inorder(root)
return answer
}
复杂度分析
- 时间复杂度：$O(n)$，两趟各访问每个节点一次。
- 空间复杂度：计入递归栈为 $O(h)$；按进阶约定不计递归栈和返回结果，额外空间为 $O(1)$。答案数组恰好包含
modeCount个值。
关键点总结
[!green]
- 第一趟只确定最高频次和答案长度，第二趟才写入答案。
- 两趟之间必须重置连续段状态，但保留第一趟确定的
maxCount。
易错点总结
[!yellow]
- 更新最大值后再执行独立的相等分支，会重复加入当前值。
- 不清旧候选，会留下频次较低的值。
- 复用 Java 对象时不重置成员状态，会混入上一次查询结果。
- 两趟方法若在中途修改已确定的
maxCount，就会破坏第二趟的收集条件。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 347. 前 K 个高频元素 | 中等 | 原题对一般数组哈希统计频次，本题中序有序可把相同值连成连续段统计。 |
| 98. 验证二叉搜索树 | 中等 | 同样利用中序顺序，本题允许重复值并计连续次数，原题通常按严格递增验证BST。 |