Day115 | 灵神 | 二叉树 | 二叉搜索树中的众数

501.二叉搜索树中的众数

501. 二叉搜索树中的众数 - 力扣（LeetCode）

思路：

直接想法：遍历一遍，然后用map统计频率，最后对value排序，选出最大的

更好地做法：

二叉搜索树中序遍历是有序的，收入到一个vector中对这个升序数组进行处理

更好一点的话，那就是中序遍历过程中动态统计频率

用MaxCnt记录最大值，用Cnt表示当前结点值的频率，用pre记录前一个节点

如果当前结点和前一个结点的值相等，那就Cnt++

如果不相等那么Cnt重新置为1，表示当前结点t是一个新值

如果Cnt大于MaxCnt的话就把MaxCnt更新为Cnt

如果二者相等的话就把当前结点的值放入结果集中

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
class Solution {
public:
    int cnt=1;
    TreeNode* pre=nullptr;
    int MaxCnt=1;
    vector<int> res;
    void tra(TreeNode *t)
    {
        if(t==nullptr)
            return ;
        tra(t->left);
        if(pre!=nullptr)
            if(pre->val==t->val)
                cnt++;
            else
                cnt=1;
        if(cnt==MaxCnt)
            res.push_back(t->val);
        else if(cnt>MaxCnt)
        {
            res.clear();
            res.push_back(t->val);
            MaxCnt=cnt;
        }
        pre=t;
        tra(t->right);
    }
    vector<int> findMode(TreeNode* root) {
        tra(root);
        return res;
    }
};