算法力扣刷题记录 五十六【501.二叉搜索树中的众数】

前言

二叉搜索树操作，继续。
记录 五十六【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

进阶：你可以不使用额外的空间吗？（假设由递归产生的隐式调用栈的开销不被计算在内）

---

二、尝试实现

依然使用二叉搜索树中序遍历得到有序递增序列的特性。

思路【直白想法】

1. 借助数组，通过中序遍历将二叉搜索树中的值取出来。再在数组中操作。
2. 在数组中使用双指针循环，判断一个值出现的次数，再和最大次数记录比较：

• 如果比最大出现次数的记录小，那么不操作；
• 如果相等，那么加入到返回值数组中；
• 如果比最大出现次数的记录大，判断返回值数组中是否为空，先清空后加入。

代码实现【借助数组，额外开辟空间】

/*** 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,vector<int>& nums){if(!cur) return;traversal(cur->left,nums);nums.push_back(cur->val);traversal(cur->right,nums);return;}vector<int> findMode(TreeNode* root) {vector<int> result;vector<int> nums;traversal(root,nums);int max = 0;for(int i = 0;i < nums.size();){int j=i+1;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,vector<int>& 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;}vector<int> findMode(TreeNode* root) {vector<int> result;traversal(root,result);//处理最后}
};

使用时候，如何结束时也能操作元素呢？在cur->right后还有处理逻辑。

学习内容

1. 双指针法解决：先说误区

• 从借助数组的代码实现中发现遍历数组时，使用了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。

2. 双指针代码修正：

class Solution {
public:int maxcount = 0;//记录最大次数int count = 1;//计数。TreeNode* pre =  nullptr;void traversal(TreeNode* cur,vector<int>& 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;}vector<int> findMode(TreeNode* root) {vector<int> result;traversal(root,result);return result;}
};

3. 迭代法：中序迭代模版，加中间节点处理逻辑。
4. 普通二叉树如何求众数？

• 普通二叉树数值没有任何关系，那么双指针法不成立。不过借助数组方法依然可以用。
• 借助数组：遍历取出所有值放到vector里面，之后sort从小到大排个序，遍历数组；
• 参考借助数组思路：用unordered_map统计元素出现次数，再把map转换成vector，再自定义比较函数，带入sort中，得到从大到小的排序vector。

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,unordered_map<int,int>& nums){if(!cur) return;nums[cur->val]++;traversal(cur->left);traversal(cur->right);}bool cmp(const pair<int,int>& a,const pair<int,int>& b) const{return a.second > b.second;}vector<int> findMode(TreeNode* root) {vector<int> result;unordered_map<int,int> map;traversal(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 = 0;i <vec.size();i++){if(vec[i].second == vec[0].second) result.push_back(vec[i].first);}return result;}
};

---

总结

【501.二叉搜索树中的众数】和【求普通二叉树的众数】

（欢迎指正，转载标明出处）