501. 二叉搜索树中的众数
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1：
输入：root = [1,null,2,2]
输出：[2]示例 2：
输入：root = [0]
输出：[0]提示：
- 树中节点的数目在范围
[1, 104]内 -105 <= Node.val <= 105
进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）
题解
利用二叉搜索树的性质，进行中序遍历，得到一个升序序列。通过遍历cnt累计当前节点出现的次数，maxCnt记录最多次数。vector存储众数，通过变量lastVal与当前节点值对比，判断cnt是否继续累加。
- 当
cnt>maxCnt时更新最大值，并且清空vector,存入当前节点、 - 当
cnt=maxCnt时,存入当前节点，不需要清空。
查看代码
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> findMode(TreeNode* root) {
vector<int> res;
int cnt=0;//累计当前节点出现次数
int maxxCnt=0;//最大出现次数
int lastVal=root->val;//中序遍历上一个节点的值
while (root != NULL)
{
if (root->left == NULL)
{
// cout << root->val << " ";//输出当前节点
if(lastVal==root->val)
cnt++;
else{
cnt=1;
lastVal=root->val;
}
if(cnt>maxxCnt){//更新res和maxxCnt
res.clear();//清空res
res.emplace_back(root->val);
maxxCnt=cnt;
}else if(cnt==maxxCnt)//多个众数
{
res.emplace_back(root->val);
}
root = root->right;
}
else
{
// 找当前节点的前趋结点
TreeNode* predecessor = root->left;
while (predecessor->right != NULL
&& predecessor->right != root)
{
predecessor = predecessor->right;
}
// 使当前节点成为inorder的前序节点的右侧子节点
if (predecessor->right == NULL)
{
predecessor->right = root;
root = root->left;
}
//复原之前的修改
else
{
predecessor->right = NULL;
// cout << root->val << " ";//输出当前节点
if(lastVal==root->val)
cnt++;
else{
cnt=1;
lastVal=root->val;
}
if(cnt>maxxCnt){//更新res和maxxCnt
res.clear();//清空res
res.emplace_back(root->val);
maxxCnt=cnt;
}else if(cnt==maxxCnt)//多个众数
{
res.emplace_back(root->val);
}
root = root->right;
}
}
}
return res;
}
};