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

前言

二叉搜索树操作，继续。
记录 五十六【501.二叉搜索树中的众数】

---

一、题目阅读

给你一个含重复值的二叉搜索树（BST）的根节点 root ，找出并返回 BST 中的所有 众数（即，出现频率最高的元素）。

如果树中有不止一个众数，可以按 任意顺序 返回。

假定 BST 满足如下定义：

结点左子树中所含节点的值 小于等于 当前节点的值
结点右子树中所含节点的值 大于等于 当前节点的值
左子树和右子树都是二叉搜索树

示例 1：

输入：root = [1,null,2,2]
输出：[2]
1
2

示例 2：

输入：root = [0]
输出：[0]
1
2

提示：

树中节点的数目在范围 [1, 10^4] 内
-10^5 <= Node.val <= 10^5
1
2

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

---

二、尝试实现

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

思路【直白想法】

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

---

三、参考学习

参考学习链接

学习目标：如何在树中边遍历边确定众数？肯定还是双指针。尝试一下：有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);
        //处理最后
        

    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

使用时候，如何结束时也能操作元素呢？在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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

---

总结

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

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