508. Most Frequent Subtree Sum

發表於 | 分類於

problem

solution

option 1

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
class Solution {
public:
    unordered_map<int,int> memo;
    void postorder(TreeNode *root){
        if(!root) return;
        
        postorder(root->left);
        postorder(root->right);
        
        if(root->left) root->val += root->left->val;
        if(root->right) root->val += root->right->val;
        memo[root->val]++;
        
    }
    vector<int> findFrequentTreeSum(TreeNode* root) {
        postorder(root);
        vector<pair<int,int>> freq;
        int maxFreq = 0;
        for(auto m:memo){
            maxFreq = max(maxFreq, m.second);
            freq.push_back({m.first, m.second});
        } 
        sort(freq.begin(), freq.end(), [](const auto &a, const auto &b){
            return a.second>b.second;
        });
        vector<int> ans;
        for(auto f:freq){
            if(f.second ==maxFreq) ans.push_back(f.first);
            else break;
        }
        return ans;
    }
};

option 2 - optimization option 1

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
class Solution {
public:
    unordered_map<int,int> memo;
    vector<int> ans;
    int maxFreq;
    void postorder(TreeNode *root){
        if(!root) return;
        
        postorder(root->left);
        postorder(root->right);
        
        if(root->left) root->val += root->left->val;
        if(root->right) root->val += root->right->val;
        memo[root->val]++;
        
        if(memo[root->val] >= maxFreq){
            if(memo[root->val] > maxFreq) ans.clear();
            ans.push_back(root->val);
            maxFreq = memo[root->val];
        }
    }
    vector<int> findFrequentTreeSum(TreeNode* root) {
        maxFreq = 0;
        postorder(root);
        return ans;
    }
};

analysis

  • time complexity O(n)
  • space complexity O(n)