Day115 | 灵神 | 二叉树 | 二叉搜索树中的众数

Day115 | 灵神 | 二叉树 | 二叉搜索树中的众数

501.二叉搜索树中的众数

501. 二叉搜索树中的众数 - 力扣（LeetCode）

思路：

直接想法：遍历一遍，然后用map统计频率，最后对value排序，选出最大的

更好地做法：

二叉搜索树中序遍历是有序的，收入到一个vector中对这个升序数组进行处理

更好一点的话，那就是中序遍历过程中动态统计频率

用MaxCnt记录最大值，用Cnt表示当前结点值的频率，用pre记录前一个节点

如果当前结点和前一个结点的值相等，那就Cnt++

如果不相等那么Cnt重新置为1，表示当前结点t是一个新值

如果Cnt大于MaxCnt的话就把MaxCnt更新为Cnt

如果二者相等的话就把当前结点的值放入结果集中

class Solution {
public:int cnt=1;TreeNode* pre=nullptr;int MaxCnt=1;vector<int> res;void tra(TreeNode *t){if(t==nullptr)return ;tra(t->left);if(pre!=nullptr)if(pre->val==t->val)cnt++;elsecnt=1;if(cnt==MaxCnt)res.push_back(t->val);else if(cnt>MaxCnt){res.clear();res.push_back(t->val);MaxCnt=cnt;}pre=t;tra(t->right);}vector<int> findMode(TreeNode* root) {tra(root);return res;}
};