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
}