# 508. Most Frequent Subtree Sum

• Time: $O(n)$
• Space: $O(n)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public: vector findFrequentTreeSum(TreeNode* root) { vector ans; unordered_map 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& count) { if (root == nullptr) return 0; const int sum = root->val + sumDownFrom(root->left, count) + sumDownFrom(root->right, count); ++count[sum]; return sum; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 class Solution { public int[] findFrequentTreeSum(TreeNode root) { List ans = new ArrayList<>(); Map 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) ans.add(sum); return ans.stream().mapToInt(Integer::intValue).toArray(); } private int sumDownFrom(TreeNode root, Map 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; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 class Solution: def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]: if not root: return [] count = collections.Counter() def dfs(root: Optional[TreeNode]) -> int: if not root: return 0 summ = root.val + dfs(root.left) + dfs(root.right) count[summ] += 1 return summ dfs(root) maxFreq = max(count.values()) return [summ for summ in count if count[summ] == maxFreq]