二叉搜索树中的众数
任意二叉树map排序版
先遍历树，然后记录到map中。
之后将map存到vector中，因为map无法排序
对vector中pair的value排序
最后取最大的
/** * 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: //谓词，排序pair vector class compare { public: bool operator() (pair<int,int>p1 , pair<int,int>p2) { return p1.second > p2.second; } }; unordered_map<int,int>my_map; //递归遍历 void tarvelsal(TreeNode* cur) { if(cur==nullptr) return; tarvelsal(cur->left); my_map[cur->val]++; tarvelsal(cur->right); } vector<int> findMode(TreeNode* root) { vector<pair<int,int>> nums; vector<int> result; tarvelsal(root); //map复制到vector for(auto it:my_map) { nums.push_back(pair(it.first , it.second)); } sort(nums.begin() , nums.end() , compare()); //找最大的 for(int i=0 ; i<nums.size() ; i++) { if(nums[i].second == nums[0].second ) result.push_back(nums[i].first); } return result; } };
二叉搜索树
/** * 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: //当前值重复次数 int count = 0; //最大值重复次数 int max_count = 0; vector<int> result; TreeNode* pre = nullptr; //中序递归，二叉搜索树是从小到达排序 void max_count_tree(TreeNode* cur) { if(cur == nullptr) return ; max_count_tree(cur->left); //如果当前次数是0，则是根节点，记录次数为1 if(count==0) count=1; //如果当前值和旧值相同，次数加1 else if(count!=0 && pre->val == cur->val) count++; //如果次数不为零，又发现当前值和旧值不同，则遇到新值。复位记录次数为1 else count =1; //更新旧点 pre = cur; //如果当前迭代次数和最大次数相同，此值加入结果 if(count == max_count) { result.push_back(cur->val); } //如果当前次数大于之前的最大次数，则更新结果 //之前的旧结果要清除，重新添加 if(count > max_count) { max_count = count; result.clear(); result.push_back(cur->val); } max_count_tree(cur->right); } vector<int> findMode(TreeNode* root) { max_count_tree(root); return result; } };
二刷
/** * 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: vector<int> result; TreeNode* pre = nullptr; int num_times = 0 , max_times = 0; void track_back(TreeNode *cur) { if(cur == nullptr) return; track_back(cur->left); if(pre == nullptr) { num_times = 1; }else if( pre->val == cur->val) { num_times++; }else if(pre->val != cur->val) { num_times = 1; } if(num_times > max_times) { max_times = num_times; result.clear(); result.push_back(cur->val); }else if(num_times == max_times) { result.push_back(cur->val); } pre = cur; track_back(cur->right); } vector<int> findMode(TreeNode* root) { track_back( root); return result; } };
