0501. Find Mode in Binary Search Tree
=====================================
题目信息
--------
:题号: 0501
:难度: Easy
:主题: 二叉搜索树、频率统计、并列众数
:原题: `LeetCode 0501 `_
:重点: BST 允许重复值、众数按出现次数定义、可能存在多个并列众数、结果顺序不限
题目重述
--------
给定一棵允许出现重复值的二叉搜索树,找出树中出现次数最多的所有节点值。若多个不同值具有相同的最高频率,需要全部返回,排列顺序不限。
树中节点数位于 ``[1, 10^4]``,节点值位于 ``[-10^5, 10^5]``。统计对象是节点值的出现次数,而不是节点引用;同一个值在不同节点中出现时需要累计。
自建示例
--------
存在多个并列众数:
.. code-block:: text
输入:root = [4,2,6,2,3,5,6]
输出:[2,6]
解释:数值 2 和 6 都出现两次,其余数值各出现一次,因此二者都是众数;返回顺序可以交换。
只有一个节点:
.. code-block:: text
输入:root = [9]
输出:[9]
解释:树中唯一的值自然具有最高频率。
利用中序遍历的连续相同值
------------------------
BST 的中序遍历按非递减顺序访问节点,因此同一个值会形成连续的一段。扫描这段序列时维护当前值及其连续出现次数;次数超过历史最大值就清空答案并换成当前值,次数相等则追加当前值。这样无需单独的频率哈希表,也能处理允许重复值的 BST。
代码使用 Morris 中序遍历,把临时线索接到当前节点的前驱上,访问完左子树后立即恢复指针。遍历结束时树的结构与输入相同,且不依赖递归栈。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
std::vector findMode(TreeNode* root) {
std::vector result;
TreeNode* current = root;
int previous = 0;
int run = 0;
int best = 0;
bool hasPrevious = false;
auto visit = [&](int value) {
if (!hasPrevious || value != previous) {
previous = value;
run = 1;
hasPrevious = true;
} else {
++run;
}
if (run > best) {
best = run;
result.clear();
result.push_back(value);
} else if (run == best) {
result.push_back(value);
}
};
while (current != nullptr) {
if (current->left == nullptr) {
visit(current->val);
current = current->right;
continue;
}
TreeNode* predecessor = current->left;
while (predecessor->right != nullptr &&
predecessor->right != current) {
predecessor = predecessor->right;
}
if (predecessor->right == nullptr) {
predecessor->right = current;
current = current->left;
} else {
predecessor->right = nullptr;
visit(current->val);
current = current->right;
}
}
return result;
}
};
代码分析
--------
把问题先从“树上的频率统计”转换成“有序序列中的连续段统计”。BST 的中序遍历会按非递减顺序输出节点值;即使树允许重复值,相同值也一定连续出现。因此,某个值在整棵树中的出现次数,正好就是中序序列中对应连续段的长度,不必为每个值再建立哈希表。
扫描中序序列的前缀时,``previous`` 和 ``run`` 描述当前连续段,``best`` 记录已经见过的最大段长。若当前段长度超过 ``best``,旧答案全部失效;若恰好等于 ``best``,当前值与旧众数并列。一个值在有序序列中只有一个连续段,所以它只会在段长第一次达到当前最高值时加入一次答案;后续相同值只会让 ``run`` 继续增加,若超过最高值则清空并重新建立答案。
代码没有使用递归中序,而是使用 Morris 遍历。当前节点没有左子树时可以立即访问;有左子树时,先找到左子树最右节点作为前驱,第一次遇到当前节点就建立一条临时线索并转入左子树,第二次沿线索返回时删除线索、访问当前节点,再转向右子树。这个过程既保持了中序顺序,也把递归栈省为常量空间。每条线索在离开对应子树时都会恢复,因此函数返回后不会改变原树结构。
以中序序列 ``[2,2,3,4,5,6,6]`` 为例:值 2 的连续段长度为 2,值 6 的连续段后来也达到 2,于是答案保留 ``[2,6]``;如果某个后续段达到 3,就说明此前所有长度 2 的值都不再是众数,答案会先清空,再只保留这个长度 3 的值。
正确性可以分成三点:中序序列中的连续段长度等于对应值的总频率;``run`` 与 ``best`` 的更新规则恰好保留所有且仅保留最高频率值;Morris 遍历恰好访问每个节点一次并恢复所有临时指针。因此最终返回的集合就是整棵树的全部众数。
``visit`` 只负责维护一个连续段和答案,Morris 主循环只负责按中序顺序提供节点值,二者职责分离且与上述不变量一一对应。每个节点至多被建立线索、恢复线索并访问一次,时间复杂度为 ``O(n)``;除返回结果外,临时线索和局部变量占用 ``O(1)`` 额外空间。