Leetcode 508: Most Frequent Subtree Sum

https://leetcode.com/problems/most-frequent-subtree-sum/description/

Notes:

We need a  hash table to count the frequencies of each possible sum. Once we have this information, then we can easily find the one(s) with the maximum frequency.

So the problem becomes how to effectively find the sum of all the subtrees.

Bottom-up recursion method would be a good choice: if we have calculated the sums of both the left and the right parts, then we just need to add them with the value of the root to get the total sum of the this sub-tree. Bottom-up recursion naturally gives the sums of all the subtrees in the tree.

The T-C is O(N), and the S-C is O(N) too. N is the number of nodes in the tree.

See the code below:

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */

class Solution {
public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        vector<int> res;
        ct = 0;
        dfs(root);
   //     cout<<ct<<endl;
        for(auto &a : mp) {
            if(a.second == ct) res.push_back(a.first);
        }
        return res;
    }

private:
    unordered_map<int, int> mp; //<sum, count>
    int ct;
    int dfs(TreeNode* r) {
        if(!r) return 0;
        int a = dfs(r->left), b = dfs(r->right), sum = a + b + r->val;
        ct = max(ct, ++mp[sum]);
        return sum;
    }
};