508. Most Frequent Subtree Sum

这道题没什么难度，我用的map，注意需要熟悉map建立、iterator遍历、map插入返回值等。

我的做法

/**
 * 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:
    int countSum (TreeNode* root, map<int, int>& findFre){
        if(root == NULL)
            return 0;
        int total = countSum(root->left, findFre) + countSum(root -> right, findFre) + root -> val;
        if(!findFre.emplace(total, 1).second)
            ++findFre[total];
        return total;
    }
    vector<int> findFrequentTreeSum(TreeNode* root) {
        vector<int> output;
        int most = 0;
        
        map<int, int> findFre;
        countSum (root, findFre);
        
        for(map <int, int>::iterator i = findFre.begin(); i != findFre.end(); i ++){
            if (i->second > most)
                most = i -> second;
        }
        for(map <int, int>::iterator i = findFre.begin(); i != findFre.end(); i ++){
            if (i -> second == most)
                output.push_back(i -> first);
        }
        return output;
    }
};

他人解法

发现写法优雅但是比我慢。。。谜。。。leetcode不能查看最快的提交吗。。。

class Solution {
public:
    vector<int> findFrequentTreeSum(TreeNode* root) {
        unordered_map<int,int> counts;
        int maxCount = 0;
        countSubtreeSums(root, counts, maxCount);
        
        
        vector<int> maxSums;
        for(const auto& x :  counts){
            if(x.second == maxCount) maxSums.push_back(x.first);
        }
        return maxSums;
    }
    
    int countSubtreeSums(TreeNode *r, unordered_map<int,int> &counts, int& maxCount){
        if(r == nullptr) return 0;
        
        int sum = r->val;
        sum += countSubtreeSums(r->left, counts, maxCount);
        sum += countSubtreeSums(r->right, counts, maxCount);
        ++counts[sum];
        maxCount = max(maxCount, counts[sum]);
        return sum;
    }
};

这个地方的

++counts[sum];

似乎如果查询不到就会新建？