Short Clean C++ O(n) Solution

  • 13
    class Solution {
        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);
            maxCount = max(maxCount, counts[sum]);
            return sum;

  • 0

    @kevin36 Thank you.

  • 0

    said in Short Clean C++ O(n) Solution:


    thank you
    but, do ++count[sum] be O(1) ?
    it need to searh sum first

  • 0

    Hashtable look ups are O(1)

  • 0

    @kevin36 said in Short Clean C++ O(n) Solution:

    Hashtable look ups

    I see. Thank you.
    Nice program~

  • 0

    Thank you for your code. I'm just wondering that why "++counts[sum];" works when the key sum doesn't exist in counts. Does it only work in map?

  • 0

    When there is no key in the map the default constructor is called for the value, in this case we it is initialized to zero

  • 0

    @kevin36 Got it. Thank you!

  • 1
        int sumTree(TreeNode* root, vector<int> &res, map<int, int> &hash, int &m){
            if(!root) return 0;
            int cur = root->val + sumTree(root->left, res,hash, m) + sumTree(root->right, res,hash, m);
            if(hash[cur] > m){ res.clear(); res.push_back(cur); m=hash[cur]; }
            else if(hash[cur]==m) res.push_back(cur);
            return cur;
        vector<int> findFrequentTreeSum(TreeNode* root) {  // 508
            //if(!root) return vector<int>();
            vector<int> res;
            int m=INT_MIN;
            map<int, int> hash;
            sumTree(root, res, hash, m);
            return res;

  • 0

    more concise solution,thanks

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.