力扣501题最优解：不用额外空间找出BST中的众数？这个解法让你大开眼界
2天前
题目解读：
在二叉搜索树的世界里，每个节点都默默记录着自己的数值。现在我们需要找出这些数值中出现频率最高的那些数字，也就是所谓的"众数"。有趣的是，二叉搜索树本身具有左小右大的特性，这为我们解决问题提供了天然的便利。题目要求我们找出所有出现次数最多的元素，当多个数字出现次数相同时，需要全部返回。
解题思路：
采用中序遍历+频率统计的经典解法。首先通过中序遍历将BST的所有节点值按升序存入数组，这个过程中BST的有序特性得到了充分利用。接着，代码使用一个足够大的数组来统计每个数值出现的频率，这里巧妙地将数值范围[-100000,100000]映射到数组索引[0,200000]。统计完所有数值的频率后，找出最大出现次数，最后收集所有达到这个最大次数的数值。这种方法虽然使用了额外空间，但思路清晰，实现简单，是解决此类问题的典型范例。
代码注释：
class Solution {
public:
vector<int> tree; // 存储中序遍历结果的容器
int sum[200001]={0}; // 频率统计数组，覆盖[-100000,100000]范围
// 中序遍历二叉搜索树
void inorder(TreeNode* root) {
if(!root) return; // 递归终止条件
inorder(root->left); // 遍历左子树
tree.push_back(root->val); // 将当前节点值加入数组
inorder(root->right); // 遍历右子树
}
vector<int> findMode(TreeNode* root) {
vector<int> ret; // 结果容器
inorder(root); // 执行中序遍历
// 统计每个数值出现的频率
for(int i=0;i<tree.size();i++)
sum[tree[i]+100000]++; // 数值+100000映射到数组索引
int maxsum=0; // 记录最大出现次数
// 找出最大出现次数
for(int i=0;i<200001;i++)
maxsum=max(maxsum,sum[i]);
// 收集所有出现次数等于maxsum的数值
for(int i=0;i<200001;i++)
if(sum[i]==maxsum) ret.push_back(i-100000); // 还原原始数值
return ret; // 返回结果
}
};原创内容 转载请注明出处
