欧美做暖网站,90设计素材网官网,新月直播,成都企业网站公司前言
二叉搜索树操作#xff0c;继续。 记录 五十六【501.二叉搜索树中的众数】 一、题目阅读
给你一个含重复值的二叉搜索树#xff08;BST#xff09;的根节点 root #xff0c;找出并返回 BST 中的所有 众数#xff08;即#xff0c;出现频率最高的元素#xff09;…前言
二叉搜索树操作继续。 记录 五十六【501.二叉搜索树中的众数】 一、题目阅读
给你一个含重复值的二叉搜索树BST的根节点 root 找出并返回 BST 中的所有 众数即出现频率最高的元素。
如果树中有不止一个众数可以按 任意顺序 返回。
假定 BST 满足如下定义
结点左子树中所含节点的值 小于等于 当前节点的值 结点右子树中所含节点的值 大于等于 当前节点的值 左子树和右子树都是二叉搜索树
示例 1
输入root [1,null,2,2]
输出[2]示例 2
输入root [0]
输出[0]提示
树中节点的数目在范围 [1, 10^4] 内
-10^5 Node.val 10^5进阶你可以不使用额外的空间吗假设由递归产生的隐式调用栈的开销不被计算在内 二、尝试实现
依然使用二叉搜索树中序遍历得到有序递增序列的特性。
思路【直白想法】
借助数组通过中序遍历将二叉搜索树中的值取出来。再在数组中操作。在数组中使用双指针循环判断一个值出现的次数再和最大次数记录比较
如果比最大出现次数的记录小那么不操作如果相等那么加入到返回值数组中如果比最大出现次数的记录大判断返回值数组中是否为空先清空后加入。
代码实现【借助数组额外开辟空间】
/*** 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 traversal(TreeNode* cur,vectorint nums){if(!cur) return;traversal(cur-left,nums);nums.push_back(cur-val);traversal(cur-right,nums);return;}vectorint findMode(TreeNode* root) {vectorint result;vectorint nums;traversal(root,nums);int max 0;for(int i 0;i nums.size();){int ji1;int count 1;for(;j nums.size();j){if(nums[j] nums[i]){count;}else{break;}}if(count max){if(!result.empty()) result.clear();result.push_back(nums[i]);max count;}else if(count max){result.push_back(nums[i]);}i j;}return result;}
};三、参考学习
参考学习链接
学习目标如何在树中边遍历边确定众数肯定还是双指针。尝试一下有bug
class Solution {
public:int maxcount 0;//记录最大次数int count 1;//计数。TreeNode* pre nullptr;void traversal(TreeNode* cur,vectorint nums){if(!cur) return;traversal(cur-left,nums);if(pre pre-val cur-val){count;}else if(pre pre-val ! cur-val){if(count maxcount){if(!nums.empty()) nums.clear();nums.push_back(pre-val);maxcount count;//最大值更新}else if(count maxcount){nums.push_back(pre-val);}count 1;//重新计数新的值pre cur;//此处才更新pre}else if(!pre){pre cur;//初始时避免pre空}traversal(cur-right,nums);return;}vectorint findMode(TreeNode* root) {vectorint result;traversal(root,result);//处理最后}
};使用时候如何结束时也能操作元素呢在cur-right后还有处理逻辑。
学习内容
双指针法解决先说误区
从借助数组的代码实现中发现遍历数组时使用了i,j相当于i不动j移动统计这个元素出现次数。如果nums[j] ! nums[i]说明nums[i]出现次数统计完毕。接下来比较count和max。没有想到可以相邻元素比较如果相等count。count加一次和max比较一次不相等时前面的count已经放到结果里。每一次都要进行count和max比较。尝试双指针错误在于认为pre-val和cur-val不相等时才更新pre才比较count和max。正确pre紧跟cur把count和max的比较放到if外面这样count更新max更新。总结错误——元素比较不相等时统计完一个元素次数后放入结果正确——每次元素比较即使相等也要判断count和max。
双指针代码修正
class Solution {
public:int maxcount 0;//记录最大次数int count 1;//计数。TreeNode* pre nullptr;void traversal(TreeNode* cur,vectorint nums){if(!cur) return;traversal(cur-left,nums);if(pre pre-val cur-val){count;}else if(pre pre-val ! cur-val ){count 1;//重新计数新的值}pre cur;//初始时避免pre空if(count maxcount){if(!nums.empty()) nums.clear();nums.push_back(pre-val);maxcount count;//最大值更新}else if(count maxcount){nums.push_back(pre-val);}traversal(cur-right,nums);return;}vectorint findMode(TreeNode* root) {vectorint result;traversal(root,result);return result;}
};迭代法中序迭代模版加中间节点处理逻辑。普通二叉树如何求众数
普通二叉树数值没有任何关系那么双指针法不成立。不过借助数组方法依然可以用。借助数组遍历取出所有值放到vector里面之后sort从小到大排个序遍历数组参考借助数组思路用unordered_map统计元素出现次数再把map转换成vector再自定义比较函数带入sort中得到从大到小的排序vector。
普通二叉树求众数代码实现
/*** 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 traversal(TreeNode* cur,unordered_mapint,int nums){if(!cur) return;nums[cur-val];traversal(cur-left);traversal(cur-right);}bool cmp(const pairint,int a,const pairint,int b) const{return a.second b.second;}vectorint findMode(TreeNode* root) {vectorint result;unordered_mapint,int map;traversal(root,map);vectorpairint,int vec(map.begin(),map.end());sort(vec.begin(),vec.end(),cmp);result.push_back(vec[0].first);for(int i 0;i vec.size();i){if(vec[i].second vec[0].second) result.push_back(vec[i].first);}return result;}
};总结
【501.二叉搜索树中的众数】和【求普通二叉树的众数】 欢迎指正转载标明出处
