难度简单603收藏分享切换为英文接收动态反馈
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1：
输入：root = [1,null,2,2]
输出：[2]示例 2：
输入：root = [0]
输出：[0]提示：
- 树中节点的数目在范围
[1, 104]内 -105 <= Node.val <= 105
**进阶：**你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
二叉搜索树的特性：中序遍历
很明显，考察的这道题是二叉搜索树，我们肯定离不开中序遍历，只不过我们需要注意的是，这个众数不只是一个，所以我们还得注意控制这个计数。
常规来说，我们需要遍历两次，第一次找到这个最大的出现频率 maxCount，然后第二遍再去找到出现 maxCount 的数，但是其实我们是可以一步到位的！
我们只需要遍历一次，如何做呢❓❓❓
很简单，我们遇到当前计数 count == maxCount 的时候是直接尾插到我们的结果数组 result，但是当 count > maxCount 的时候，说明之前尾插到数组中的数已经不是众数了，所以我们先将数组清空，再放入当前这个新的众数！
class Solution {
public:
void _find(TreeNode* root)
{
if(root == nullptr)
return;
// 前
_find(root->left);
// 中
// 先管理一下count
if(pre != nullptr && pre->val == root->val)
count++;
else
count = 1;
pre = root;
// 判断count和maxcount的关系进行操作
if(count == maxcount)
result.push_back(root->val);
else if(count > maxcount)
{
maxcount = count;
result.clear();
result.push_back(root->val);
}
// 后
_find(root->right);
}
vector<int> findMode(TreeNode* root)
{
_find(root);
return result;
}
private:
int maxcount = 1;
int count = 1;
TreeNode* pre = nullptr;
vector<int> result;
};