Short Clean C++ O(n) Solution


  • 13
    K
    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;
        }
    };

  • 0
    D

    @kevin36 Thank you.


  • 0
    W

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

    ++counts[sum];

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


  • 0
    K

    @wei_che
    Hashtable look ups are O(1)


  • 0
    W

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

    Hashtable look ups

    I see. Thank you.
    Nice program~


  • 0
    O

    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
    K

    @owenxbw93
    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
    O

    @kevin36 Got it. Thank you!


  • 1
    L
        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);
            hash[cur]++;
            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
    A

    @ly1123
    more concise solution,thanks


Log in to reply
 

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