秦皇岛企业网站建设,网页传奇游戏攻略,打开2345网址大全,上海设计工作室排名1、题目描述
. - 力扣#xff08;LeetCode#xff09; 要求#xff1a;给一个包含重复值的BST#xff0c;找出并返回BST中的众数(出现频次最高的元素)。 注#xff1a;如果树中有不止一个众数可以按任意顺序返回#xff0c;即如果有多个众数多个都要返回。 ps#xff1…1、题目描述
. - 力扣LeetCode 要求给一个包含重复值的BST找出并返回BST中的众数(出现频次最高的元素)。 注如果树中有不止一个众数可以按任意顺序返回即如果有多个众数多个都要返回。 ps另外要求不使用额外的空间。 2、分析 分析看起来还是要求在中序遍历的过程中就记录结果。 (1)在遍历的过程中记录每个数字出现的次数并不断更新同时维护历史所有的出现过的最大次数的数。 (2)如果最大次数被刷新就清空向量result并插入最新的众数如果当前数字出现的次数小于历史最大次数啥都不做 (3)如果当前数字出现的子树等于历史最大次数则将这个数也插进去。 class Solution {
public:TreeNode* pre NULL; //记录上一个节点(的数)int max_times 0; //记录历史最大出现的次数int cur_times 0; //记录当前数字出现的次数vectorint findMode(TreeNode* root) {vectorint res;inordertraversal(root, res);return res;}void inordertraversal(TreeNode* root, vectorint res){if(root NULL) return;inordertraversal(root-left, res); //左//中间节点的处理逻辑if(pre ! NULL root-val ! pre-val){cur_times 0;//如果出现新的数字了就直接将当前统计次数清零(随后有自加1)}pre root; //更新precur_times; //更新cur_times//超过之前记录的最大出现次数了if(cur_times max_times){ res.clear();res.push_back(root-val);max_times cur_times;//没超过只是触及我们也要记录}else if(cur_times max_times){res.push_back(root-val);}inordertraversal(root-right, res);//右}
};
3、实现代码
#include iostream
#include string
#include vector
#include algorithm
#include queue
#include stack
#include map
#include math.husing namespace std;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:TreeNode* pre NULL; //记录上一个节点(的数)int max_times 0; //记录历史最大出现的次数int cur_times 0; //记录当前数字出现的次数vectorint findMode(TreeNode* root) {vectorint res;inordertraversal(root, res);return res;}void inordertraversal(TreeNode* root, vectorint res){if(root NULL) return;inordertraversal(root-left, res); //左//中间节点的处理逻辑if(pre ! NULL root-val ! pre-val){cur_times 0;//如果出现新的数字了就直接将当前统计次数清零(随后有自加1)}pre root; //更新precur_times; //更新cur_times//超过之前记录的最大出现次数了if(cur_times max_times){ res.clear();res.push_back(root-val);max_times cur_times;//没超过只是触及我们也要记录}else if(cur_times max_times){res.push_back(root-val);}inordertraversal(root-right, res);//右}
};int main()
{Solution s1;/*TreeNode node4(1);TreeNode node5(3);TreeNode node3(5);TreeNode* pnode2 new TreeNode(2, node4, node5);TreeNode root(4, pnode2, node3);
*/TreeNode node3(2);TreeNode* pnode2 new TreeNode(2, node3, NULL);TreeNode* pnode1 new TreeNode(1, NULL, pnode2);vectorint res s1.findMode(pnode1);for(int num:res){cout num ,;}cout endl;}
