# Python easy understand solution

• I have used a hash-map `ctr` to count the sum occurrence.

I have wrote a sub function `countSubtreeSum` to travel through a tree and return the sum of the tree.

In `countSubtreeSum`, I will travel through the left node and the right node, calculate the sum of the tree, increment the counter `ctr`, and return the sum.

``````  def findFrequentTreeSum(self, root):
if root == None: return []

def getSum(node):
if node == None: return 0
s = node.val + getSum(node.left) + getSum(node.right)
c[s] += 1
return s

c = collections.Counter()
getSum(root)
frequent = max(c.values())
return [s for s in c.keys() if c[s] == frequent]
``````

Please upvote if it makes sense.

Update: I have changed a little to make the variable name shorter.

• @lee215
I had the exact same concept.

``````   def findFrequentTreeSum(self, root):
if not root: return []
c = Counter()

def getSum(node):
if not node: return 0
s = node.val + getSum(node.left) + getSum(node.right)
c[s] += 1
return s

getSum(root)
m = max(c.values())
return [s for s in c.keys() if c[s] == m]
``````

By the way you have a typo in your solution. `countSubtreeSum` in your helper function should be `countTreeSum`.

• C++ version

``````#include <unordered_map>
class Solution {
std::unordered_map<int, int> freqMap;
public:
vector<int> findFrequentTreeSum(TreeNode* root) {
std::vector<int> r;
if (root == nullptr){
return r;
}
sum(root);
int maxFreq = -1;
for (const auto& pair: freqMap){
if (pair.second > maxFreq)
maxFreq = pair.second;
}
for (const auto& pair: freqMap){
if (pair.second == maxFreq)
r.push_back(pair.first);
}
return r;

}

int sum(TreeNode* root){
auto s = root->val
+ (root->left == nullptr? 0 : sum(root->left))
+ (root->right == nullptr? 0: sum(root->right));
freqMap[s]++;
return s;
}
};``````

• Same idea, couple of variations:

• `filter` instead of list comprehension based filter. (Just for fun)
• `defaultdict` instead of `Counter`. ( `defaultdict` performs better than `Counter` )
``````    def findFrequentTreeSum(self, root):
if root is None: return []
freq = collections.defaultdict(int)

def dfs(root):
if root is None: return 0
s = dfs(root.left) + dfs(root.right) + root.val
freq[s] += 1
return s

dfs(root)
mx_freq = max(freq.values())
return filter(lambda s: freq[s] == mx_freq, freq.keys())
``````

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