# Short Clean C++ O(n) Solution

• ``````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;
}
};``````

• @kevin36 Thank you.

• 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

• @wei_che
Hashtable look ups are O(1)

• Hashtable look ups

I see. Thank you.
Nice program~

• 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?

• @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

• @kevin36 Got it. Thank you!

• ``````    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;
}
``````

• @ly1123
more concise solution,thanks

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