501.二叉搜索树中的众数

发表于： 分类于：
字数： 986 阅读：≈ 2分钟

🍌 501.二叉搜索树中的众数

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

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

假定 BST 满足如下定义：

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

思路

基本思想

为了求众数，肯定需要统计每个数出现的次数，为了方便起见，相同的元素相邻统计起来肯定更方便，由于是二叉搜索树，所以中序遍历就可以使得到的序列是有序序列

得到有序序列之后，一旦当前节点是新节点，就需要重新统计出现的次数，如果是旧节点，那么直接将出现的频率加一即可，有一种特殊情况，初始状态下默认为新节点，也需要重新统计出现的次数

统计完当前节点的频率，就需要判断当前节点出现的频率是否闭最大频率还大，从而判断是否需要更新结果容器，最大频率初始状态下为-1，使得结果容器可以正常更新，如果当前节点出现的频率已经大于最大频率，就需要更新结果容器，之后在进行后续的统计

当前节点出现的频率与最大频率相同也需要更新结果容器，此时直接加入结果容器中即可

为了实现判断是否出现的是新节点，需要在中序遍历的基础上增加一个pre节点记录上一次遍历的节点，从而判断当前节点是否为新节点

执行流程

  1. 中序遍历二叉树
  2. 更新当前节点出现的频率
  3. 判断频率是否大于等于最大频率
    1. 大于当前频率，容器需要清空，存储出现频率更大的节点
    2. 等于当前频率，直接将当前节点加入容器
  4. 更新pre节点
  5. 返回最终的结果

代码

根据以上分析，得出以下代码：

 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

class Solution {
public:
    //统计出出现次数最多的数
    vector<int> res;
    //统计当前数出现的次数
    int count=0;
    //统计出现的最大次数
    int max=-1;
    //用来判断当前节点是否是新节点
    TreeNode* pre;
    vector<int> findMode(TreeNode* root) {
        if(root==nullptr)
            return res;
        help(root);
        return res;
    }
    void help(TreeNode* root){
        if(root==nullptr)
            return;
        help(root->left);
        //中序遍历处理当前节点

        //统计当前数出现的次数
        //遇到新节点
        if(pre==nullptr||root->val!=pre->val)
            count=1;
        //遇到旧节点
        else
            count++;
        //统计完成当前节点出现的次数时，判断是否出现的频率更高
        if(count>max){
            res.clear();
            res.push_back(root->val);
            //更新最大的出现次数
            max=count;
        }
        //当出现不止一个众数也加入结果容器中
        else if(max==count)
            res.push_back(root->val);
        pre=root;


        help(root->right);
    }
};

总结

中序遍历二叉树，当前节点更新完出现的频率之后，判断当前频率是否大于最大频率从而判断是否更新结果容器，只要大于等于都需要更新，大于必须清空容器，因为当前容器中存放的元素出现的频率小于当前节点出现的频率