501. Find Mode in Binary Search Tree

Description

image-20210818222230366

image-20210818222248662

Solution

Imagine how we find mode in an array [1 2 2 4 5 6 6 7], we just scan over then use some variables recording the most frequent number. In this BST, we can use inorder-traversal to get this sorted array.

Code

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
class Solution {
public:
    int maxfreq, prev, curfreq;
    vector<int> res;
    vector<int> findMode(TreeNode* root) {
        dfs(root);
        return res;
    }

    void dfs(TreeNode* root){
        if(root == nullptr)
            return;
        dfs(root->left);
        if(maxfreq == 0){
            prev = root->val;
            curfreq += 1;
        }else{
            if(prev == root->val){
                curfreq+=1;
            }else{
                curfreq = 1;
                prev = root->val;
            }
        }
        if(curfreq > maxfreq){
            while(res.size()>0)
                res.pop_back();
            res.push_back(root->val);
            maxfreq = curfreq;
        }else if(curfreq == maxfreq){
            res.push_back(root->val);       
        }
        dfs(root->right);
    }
};