501.二叉搜索树中的众数
给出具有相同值的二叉树(BST )，找出BST内的所有最频值(出现频率最高的要素)。假设BST有以下定义：
包含在节点左侧子树中的节点的值小于等于当前节点的值的节点右侧子树中包含的节点的值大于等于当前节点的节点左侧子树和右侧子树是二叉树。 例如，如下所示。
如果给出BST [1，空值，2，2 ]，那么，
返回到[2]。
提示：大众数量超过1个时，无需考虑输出顺序
上级：可以不用额外的空间吗？ (假设不计算递归引起的隐式调用栈的开销)
主题是
思路
啊。 递归法从两个维度谈。首先在不是离过一次婚搜索树的情况下，比较该怎么解题、是离过一次婚搜索树还是怎么解题，可以加深对二叉树的理解。
如果不是
递归法
如果不是二叉搜索树
二叉搜索树，最直观的方法一定是把这棵树全部遍历，用map统计频率，排列频率，最后取前面高频元素的集合。具体步骤如下：
这棵树都扫描了。 即使用map统计频率，关于进行前中后序那样的扫描也不重要。 因为，要进行全扫描。 任何扫描法都可以，层序扫描也没有问题。
在本例中，代码使用前置路径，如下所示：
//mapint、intkey:元素、值：的出现频率
voidsearchbst (三节点*铁路，无顺序映射，整数映射) )//先行遍历
if (cur==空值)返回；
地图； //统计元素的频率
搜索左(cur -左，地图)；
搜索基站(cur-right，地图)；
返回；
}
统计出现频率，即对map中的值进行排序的学生可能想直接对map中的值进行排序，但还不能。 在c中，可以使用std:map或std:multimap对密钥进行排序，但无法对值进行排序。
因此，将map转换为数组vector进行排序，当然vector中也有pairint。 int型数据的第一个int是元素，第二个int是出现频率。
代码如下所示。
Boolstaticcmp (互补、国际、互补、国际) {
returna.secondb.second； //按照频率从高到低的顺序进行排序
}
vectorpairint，Int Vec (地图. Begin )，地图.结束)；
sort(vec.begin )、vec.end )、cmp )； //给频率排序
取前面的高频要素时，由于排列vector中已经存储了按频率顺序排列的pair，所以取出前面的高频要素即可。
代码如下所示。
推回(第一次)；
for (英寸=1； ivec.size (； I ) {2}
//将最高的放入result数组
if (VEC [ I ].Second==Vec [0].Second )结果.推回) Vec [ I ] .第一个；
elsebreak；
}
返回结果；
整体的c代码如下所示。
类解决方案{2}
私有：
voidsearchbst (三节点*铁路，无顺序映射，整数映射) )//先行遍历
if (cur==空值)返回；
地图； //统计元素的频率
搜索左(cur -左，地图)；
搜索基站(cur-right，地图)；
返回；
}
Boolstaticcmp (互补、国际、互补、国际) {
returna.secondb.second；
}
公共：
vctorintfindmode (三重节点*根)
有序_
map<int, int> map; // key:元素，value:出现频率 vector<int> result; if (root == NULL) 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; } };「所以如果本题没有说是二叉搜索树的话，那么就按照上面的思路写！」
是二叉搜索树
「既然是搜索树，它中序遍历就是有序的」。
如图：
中序遍历代码如下：
void searchBST(TreeNode* cur) { if (cur == NULL) return ; searchBST(cur->left); // 左 （处理节点） // 中 searchBST(cur->right); // 右 return ; }遍历有序数组的元素出现频率，从头遍历，那么一定是相邻两个元素作比较，然后就把出现频率最高的元素输出就可以了。
关键是在有序数组上的话，好搞，在树上怎么搞呢？
这就考察对树的操作了。
在二叉树：搜索树的最小绝对差 中我们就使用了pre指针和cur指针的技巧，这次又用上了。
弄一个指针指向前一个节点，这样每次cur（当前节点）才能和pre（前一个节点）作比较。
而且初始化的时候pre = NULL，这样当pre为NULL时候，我们就知道这是比较的第一个元素。
代码如下：
if (pre == NULL) { // 第一个节点 count = 1; // 频率为1 } else if (pre->val == cur->val) { // 与前一个节点数值相同 count++; } else { // 与前一个节点数值不同 count = 1; } pre = cur; // 更新上一个节点此时又有问题了，因为要求最大频率的元素集合（注意是集合，不是一个元素，可以有多个众数），如果是数组上大家一般怎么办？
应该是先遍历一遍数组，找出最大频率（maxCount），然后再重新遍历一遍数组把出现频率为maxCount的元素放进集合。（因为众数有多个）
这种方式遍历了两遍数组。
那么我们遍历两遍二叉搜索树，把众数集合算出来也是可以的。
但这里其实只需要遍历一次就可以找到所有的众数。
那么如何只遍历一遍呢？
如果 频率count 等于 maxCount（最大频率），当然要把这个元素加入到结果集中（以下代码为result数组），代码如下：
if (count == maxCount) { // 如果和最大值相同，放进result中 result.push_back(cur->val); }是不是感觉这里有问题，result怎么能轻易就把元素放进去了呢，万一，这个maxCount此时还不是真正最大频率呢。
所以下面要做如下操作：
频率count 大于 maxCount的时候，不仅要更新maxCount，而且要清空结果集（以下代码为result数组），因为结果集之前的元素都失效了。
if (count > maxCount) { // 如果计数大于最大值 maxCount = count; // 更新最大频率 result.clear(); // 很关键的一步，不要忘记清空result，之前result里的元素都失效了 result.push_back(cur->val); }关键代码都讲完了，完整代码如下：（「只需要遍历一遍二叉搜索树，就求出了众数的集合」）
class Solution { private: int maxCount; // 最大频率 int count; // 统计频率 TreeNode* pre; vector<int> result; void searchBST(TreeNode* cur) { if (cur == NULL) return ; searchBST(cur->left); // 左 // 中 if (pre == NULL) { // 第一个节点 count = 1; } else if (pre->val == cur->val) { // 与前一个节点数值相同 count++; } else { // 与前一个节点数值不同 count = 1; } pre = cur; // 更新上一个节点 if (count == maxCount) { // 如果和最大值相同，放进result中 result.push_back(cur->val); } if (count > maxCount) { // 如果计数大于最大值频率 maxCount = count; // 更新最大频率 result.clear(); // 很关键的一步，不要忘记清空result，之前result里的元素都失效了 result.push_back(cur->val); } searchBST(cur->right); // 右 return ; } public: vector<int> findMode(TreeNode* root) { count = 0; maxCount = 0; TreeNode* pre = NULL; // 记录前一个节点 result.clear(); searchBST(root); return result; } };迭代法
只要把中序遍历转成迭代，中间节点的处理逻辑完全一样。
二叉树前中后序转迭代，传送门：
二叉树：听说递归能做的，栈也能做 二叉树：前中后序迭代方式的写法就不能统一一下么？下面我给出其中的一种中序遍历的迭代法，其中间处理逻辑一点都没有变（我从递归法直接粘过来的代码，连注释都没改，哈哈）
代码如下：
class Solution { public: vector<int> findMode(TreeNode* root) { stack<TreeNode*> st; TreeNode* cur = root; TreeNode* pre = NULL; int maxCount = 0; // 最大频率 int count = 0; // 统计频率 vector<int> result; while (cur != NULL || !st.empty()) { if (cur != NULL) { // 指针来访问节点，访问到最底层 st.push(cur); // 将访问的节点放进栈 cur = cur->left; // 左 } else { cur = st.top(); st.pop(); // 中 if (pre == NULL) { // 第一个节点 count = 1; } else if (pre->val == cur->val) { // 与前一个节点数值相同 count++; } else { // 与前一个节点数值不同 count = 1; } if (count == maxCount) { // 如果和最大值相同，放进result中 result.push_back(cur->val); } if (count > maxCount) { // 如果计数大于最大值频率 maxCount = count; // 更新最大频率 result.clear(); // 很关键的一步，不要忘记清空result，之前result里的元素都失效了 result.push_back(cur->val); } pre = cur; cur = cur->right; // 右 } } return result; } };总结
本题在递归法中，我给出了如果是普通二叉树，应该怎么求众数。
知道了普通二叉树的做法时候，我再进一步给出二叉搜索树又应该怎么求众数，这样鲜明的对比，相信会对二叉树又有更深层次的理解了。
在递归遍历二叉搜索树的过程中，我还介绍了一个统计最高出现频率元素集合的技巧， 要不然就要遍历两次二叉搜索曾经的荷花能把这个最高出现频率元素的集合求出来。
为什么没有这个技巧一定要遍历两次呢？因为要求的是集合，会有多个众数，如果规定只有一个众数，那么就遍历一次稳稳的了。
最后我依然给出对应的迭代法，其实就是迭代法中序遍历的模板加上递归法中中间节点的处理逻辑，分分钟就可以写出来，中间逻辑的代码我都是从递归法中直接粘过来的。
求二叉搜索树中的众数其实是一道简单题，但大家可以发现我写了这么一大篇幅的文章来讲解，主要是为了尽量从各个角度对本题进剖析，帮助大家更快更深入理解二叉树
「就酱，如果学到了的话，就转发给身边需要的同学吧，可能他们也需要！」
-------end-------
我将算法学习相关的资料已经整理到了
Github ：https://github.com/youngyangyang04/leetcode-master，里面还有leetcode刷题攻略、各个类型经典题目刷题顺序、思维导图，可以fork到自己仓库有空看一看一定会有所收获，顺便给一个star支持一下吧！
我是程序员Carl，哈工大tydyj，先后在腾讯和百度打杂，这里每天8:35准时推送一道经典算法题目，我选择的每道题目都不是孤立的，而是由浅入深，环环相扣，帮你梳理算法知识脉络，轻松学算法！
@代码随想录 期待你的关注