501. 二叉搜索树中的众数
题目描述:
给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。
如果树中有不止一个众数，可以按 任意顺序 返回。
假定 BST 满足如下定义：
- 结点左子树中所含节点的值 小于等于 当前节点的值
- 结点右子树中所含节点的值 大于等于 当前节点的值
- 左子树和右子树都是二叉搜索树
示例 1：
输入：root = [1,null,2,2]
输出：[2]
示例 2：
输入：root = [0]
输出：[0]
思路分析:
遇到二叉搜索树我们应该第一个想到的就是中序遍历。
直白的解法：中序遍历二叉树 ，将遍历的数据收集到一个数组 ，然后我们遍历整个数组，找到所有众数。
也可以用*map<int,int>*进行保存 （first->元素的值 ，second->元素出现的频率）。
我这里介绍双指针的解法：
我们需要定义一些全局变量来辅助我们解题。
TreeNode *preTree = nullptr; //记录当前遍历节点的前一个节点
vector<int>ret;
int maxCount = 0; //二叉树中出现的最大频率,需要更新
int count = 0; //记录每一个元素出现的频率
每遍历一个元素的时候 ，我们就对其出现的频率进行计算。
如果当前的元素 ，和他的前一个元素相等，那么对其频率 + 1 。
如果当前的元素 ，和他的前一个元素不相等，那么说明，又到了一个新的元素，将其频率置 1。
如果我们当前的数据的频率和我们最大的频率一样了 ，那么就将此元素收集起来。
对最大的频率进行更新 ，如果当前数据的频率大于我们的最大频率，将最大频率进行更新。并且说明之前我们收集的元素不是出现次数最多的 ，所有我们需要清空之前收集的元素 ，收集当前遍历到的元素。
具体代码实现：
class Solution {
public://中序遍历void find(TreeNode *root){if(!root) return ;if(root->left) find(root->left);if(!preTree){ //遍历到第一个节点count =1;}else if( preTree->val == root->val ){ //两个数相等的情况count++;}else { //不相等的情况count = 1; //将出现的频率置一}preTree = root; if(count == maxCount){ //如果当前数据出现的频率等于我们记录的最大的频率,则收集ret.push_back(root->val);}if(count > maxCount){ //说明遇到频率更大的数了maxCount = count; //更新最大的频率ret.clear(); //将之前我们搜集的元素置空ret.push_back(root->val); //加入当前频率最大的元素}if(root->right) find(root->right);}vector<int> findMode(TreeNode* root) {if(!root) return ret;find(root);return ret;}private:TreeNode *preTree = nullptr; //记录当前遍历节点的前一个节点vector<int>ret;int maxCount = 0; //二叉树中出现的最大频率,需要更新int count = 0; //记录每一个元素出现的频率
};
