二叉搜索树中的众数

1题目

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

• 结点左子树中所含节点的值 小于等于 当前节点的值
• 结点右子树中所含节点的值 大于等于 当前节点的值
• 左子树和右子树都是二叉搜索树

示例 1：

输入：root = [1,null,2,2]
输出：[2]

示例 2：

输入：root = [0]
输出：[0]

2链接

题目链接：501. 二叉搜索树中的众数 - 力扣（LeetCode）

视频链接：不仅双指针，还有代码技巧可以惊艳到你！ | LeetCode：501.二叉搜索树中的众数_哔哩哔哩_bilibili

3解题思路

如果不是二叉搜索树

如果不是二叉搜索树，最直观的方法一定是把这个树都遍历了，用map统计频率，把频率排个序，最后取前面高频的元素的集合。

具体步骤如下：

1、这个树都遍历了，用map统计频率

至于用前中后序哪种遍历也不重要，因为就是要全遍历一遍，怎么个遍历法都行，层序遍历都没毛病！

2、把统计的出来的出现频率（即map中的value）排个序

有的同学可能可以想直接对map中的value排序，还真做不到，C++中如果使用std::map或者std::multimap可以对key排序，但不能对value排序。

所以要把map转化数组即vector，再进行排序，当然vector里面放的也是pair<int, int>类型的数据，第一个int为元素，第二个int为出现频率。

3、取前面高频的元素

此时数组vector中已经是存放着按照频率排好序的pair，那么把前面高频的元素取出来就可以了。

是二叉搜索树

既然是搜索树，它中序遍历就是有序的。、

在二叉树：搜索树的最小绝对差 (opens new window)中我们就使用了pre指针和cur指针的技巧，这次又用上了。

弄一个指针指向前一个节点，这样每次cur（当前节点）才能和pre（前一个节点）作比较。

而且初始化的时候pre = NULL，这样当pre为NULL时候，我们就知道这是比较的第一个元素。

此时又有问题了，因为要求最大频率的元素集合（注意是集合，不是一个元素，可以有多个众数），如果是数组上大家一般怎么办？

应该是先遍历一遍数组，找出最大频率（maxCount），然后再重新遍历一遍数组把出现频率为maxCount的元素放进集合。（因为众数有多个）

这种方式遍历了两遍数组。

那么我们遍历两遍二叉搜索树，把众数集合算出来也是可以的。

但这里其实只需要遍历一次就可以找到所有的众数。

那么如何只遍历一遍呢？

如果 频率count 等于 maxCount（最大频率），当然要把这个元素加入到结果集中（以下代码为result数组）

result怎么能轻易就把元素放进去了呢，万一，这个maxCount此时还不是真正最大频率呢。

所以下面要做如下操作：

频率count 大于 maxCount的时候，不仅要更新maxCount，而且要清空结果集（以下代码为result数组），因为结果集之前的元素都失效了。

4代码

/*** 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:void searchBST(TreeNode* cur, unordered_map<int,int>& map) {if (cur == nullptr) return ;map[cur->val]++; //统计元素频率searchBST(cur->left, map);searchBST(cur->right, map);return ;}bool static cmp (const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second;}vector<int> findMode(TreeNode* root) {unordered_map<int, int> map; //key:元素，value:出现的频率vector<int> result;if (root == nullptr) return result;searchBST(root, map);vector<pair<int, int>> vec(map.begin(), map.end());sort(vec.begin(), vec.end(), cmp); //给频率排序result.push_back(vec[0].first);for (int i = 1; i < vec.size(); i++) {//取最高的放到result数组中if (vec[i].second == vec[0].second) result.push_back(vec[i].first);else break;}return result;}
};//双指针(pre & cur)法
class Solution {
public:int count = 0;int maxCount = 0;TreeNode* pre = nullptr;vector<int> result;void traversal (TreeNode* cur) {if (cur == nullptr) return ;//左traversal(cur->left); //中if (pre == nullptr) count = 1;else if (cur->val == pre->val) count++; //cur节点与pre节点数值相同，计数+1else count = 1; //cur节点与pre节点数值不相同，重置cur->val的计数pre = cur; //双指针依次后移if (count == maxCount) result.push_back(cur->val);// 如果和最大值相同，放进result中if (count > maxCount) {maxCount = count; //更新最大频率result.clear(); //清空result数组中储存的所有最大元素，因为找到了更大的result.push_back(cur->val); //把这个更大的元素放入result数组}//右traversal(cur->right);return ;}vector<int> findMode(TreeNode* root) {traversal(root);return result;}
};