[LeetCode] 508. Most Frequent Subtree Sum

https://leetcode.com/contest/leetcode-weekly-contest-18a/problems/most-frequent-subtree-sum/

Solution:
first step to find all the sums of the subtrees; then save the ones appearing mostly. So the first step is the key for this question.
Using the properties of Tree, we can recursively find the sums of all the subtrees in a "bottom-up" fashion. See code below.

Code:

/**
 * 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;
        unordered_map<int, int> m;
        int count = -1;
        findFTS(root, 0, m, count);
        for(auto a:m){
            if(a.second == count)
                res.push_back(a.first);
        } 
        return res;
    }
private: 
    int findFTS(TreeNode *r, int s, unordered_map<int, int> &m, int &ct){
        if(!r) return 0;
        int lt = findFTS(r->left, s, m, ct);
        int rt = findFTS(r->right, s, m, ct);
        s = lt + rt + r->val;
        ++m[s];
        ct = max(ct, m[s]);
        return s;
    }
};