• Time:O(n)
• Space:O(n)

## C++

``````class Solution {
public:
vector<int> findFrequentTreeSum(TreeNode* root) {
vector<int> ans;
unordered_map<int, int> count;
int maxCount = 0;

sumDownFrom(root, count);

for (const auto& [_, freq] : count)
maxCount = max(maxCount, freq);

for (const auto& [sum, freq] : count)
if (freq == maxCount)
ans.push_back(sum);

return ans;
}

private:
int sumDownFrom(TreeNode* root, unordered_map<int, int>& count) {
if (!root)
return 0;

const int sum = root->val + sumDownFrom(root->left, count) +
sumDownFrom(root->right, count);
++count[sum];
return sum;
}
};
``````

## JAVA

``````class Solution {
public int[] findFrequentTreeSum(TreeNode root) {
List<Integer> ans = new ArrayList<>();
Map<Integer, Integer> count = new HashMap<>();
int maxCount = 0;

sumDownFrom(root, count);

for (final int freq : count.values())
maxCount = Math.max(maxCount, freq);

for (final int sum : count.keySet())
if (count.get(sum) == maxCount)

return ans.stream().mapToInt(i -> i).toArray();
}

private int sumDownFrom(TreeNode root, Map<Integer, Integer> count) {
if (root == null)
return 0;

final int sum = root.val + sumDownFrom(root.left, count) + sumDownFrom(root.right, count);
count.merge(sum, 1, Integer::sum);
return sum;
}
}
``````

## Python

``````class Solution:
def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:
if root is None:
return []

count = Counter()

def dfs(root: Optional[TreeNode]) -> int:
if root is None:
return 0

sum = root.val + dfs(root.left) + dfs(root.right)
count[sum] += 1
return sum

dfs(root)
maxFreq = max(count.values())
return [sum for sum in count if count[sum] == maxFreq]
``````