# 2022-06-19

## 508. Most Frequent Subtree Sum

### Description

Given the `root` of a binary tree, return the most frequent subtree sum. If there is a tie, return all the values with the highest frequency in any order.

The subtree sum of a node is defined as the sum of all the node values formed by the subtree rooted at that node (including the node itself).

Example 1:

``````Input: root = [5,2,-3]
Output: [2,-3,4]``````

Example 2:

``````Input: root = [5,2,-5]
Output: [2]``````

Constraints:

• The number of nodes in the tree is in the range `[1, 10^4]`.

• `-10^5 <= Node.val <= 10^5`

### Solution

#### Approach #0

``````/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func findFrequentTreeSum(root *TreeNode) (ans []int) {
m := make(map[int]int)
var big int
var dfs func(*TreeNode) int
dfs = func(node *TreeNode) int {
if node == nil {
return 0
}
sum := node.Val + dfs(node.Left) + dfs(node.Right)
m[sum]++
if m[sum] > big {
big = m[sum]
}
return sum
}
dfs(root)

for k, v := range m {
if v == big {
ans = append(ans, k)
}
}
return
}
``````

Last updated