# 2022-06-19

## [508. Most Frequent Subtree Sum](https://leetcode.com/problems/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:**

![](https://img.content.cc/a/2022/06/19/09-55-18-226-508a6058cf402606df058c843103c9e3-7d1de7.png)

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

**Example 2:**

![](https://img.content.cc/a/2022/06/19/09-55-30-362-b0fb9e0922b7f32486e9750232b128fd-7b17ad.png)

```
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

```go
/**
 * 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
}

```