本文主要是介绍算法day17|如何求普通二叉树的众数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
算法day17|如何求普通二叉树的众数
- 501的变式：普通二叉树的众数
501的变式：普通二叉树的众数
如果把二叉搜索树变成普通二叉树，我们该怎么思考呢？这个时候就要回到我一开始的思路了，用哈希表来解决问题。
class Solution {
public:unordered_map<int,int> map;void traversal(TreeNode* root){if(root==nullptr)return;map[root->val]++;traversal(root->left);traversal(root->right);return;}bool static cmp(pair<int,int>&a,pair<int,int>&b){return a.second>b.second;}vector<int> findMode(TreeNode* root) {vector<int> result;if(root==nullptr)return result;traversal(root);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++){if(vec[i].second==vec[0].second)result.push_back(vec[i].first);elsebreak;}return result;}
};
总体思路：
- 首先，用哈希表来记录二叉树的元素及其个数
- 其次，对哈希表进行排序。由于哈希表的值是不能直接实现排序的，所以我们要**先把哈希表整个存在vector<pair<int,int>>**中，然后用sort函数来对vector排序即可（另外，sort的排序规则是需要单独写的）
- 排序之后取前面相同的项的键即可
代码细节：
- 哈希表的插入
map[root->val]++;
这是最简化的形式，map[键]，中括号内是键，而map[键]整体就是对应的值，所以可以map[“coffee”]=1;或者map[root->val]++;
-
pair<int,int>也是可以作为一种数据类型的，可以代入函数里面，也可以作为vector的数据类型。本质上和int、double没有区别
-
sort函数
sort(vec.begin(),vec.end(),cmp);
它有三个参数begin, end（区间左闭右开）, cmp。其中，cmp参数为排序规则（cmp参数可以不写，如果不写的话，默认从小到大进行排序），如果是想要从大到小的排序，则需要写greater()（即：sort(begin,end,greater())）此处我们需要另写函数，因为数据类型比较特殊。
对于pair<int,int>，函数重写格式：
bool static cmp(pair<int,int>&a,pair<int,int>&b){return a.second>b.second;}
函数开头的bool static要注意
- 如果以vector作为函数返回值的话，不能返回null
这篇关于算法day17|如何求普通二叉树的众数的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
