0508. Most Frequent Subtree Sum

# 508. Most Frequent Subtree Sum#

## 题目 #

Given the root of a tree, you are asked to find the most frequent subtree sum. 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). So what is the most frequent subtree sum value? If there is a tie, return all the values with the highest frequency in any order.

Examples 1

Input:

``````  5
/  \
2   -3
``````

return [2, -3, 4], since all the values happen only once, return all of them in any order.

Examples 2

Input:

``````  5
/  \
2   -5
``````

return [2], since 2 happens twice, however -5 only occur once.

Note: You may assume the sum of values in any subtree is in the range of 32-bit signed integer.

## 解题思路 #

• 给出一个树，要求求出每个节点以自己为根节点的子树的所有节点值的和，最后按照这些和出现的频次，输出频次最多的和，如果频次出现次数最多的对应多个和，则全部输出。
• 递归找出每个节点的累加和，用 map 记录频次，最后把频次最多的输出即可。

## 代码 #

``````
package leetcode

import (
"sort"
)

/**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/

// 解法一 维护最大频次，不用排序
func findFrequentTreeSum(root *TreeNode) []int {
memo := make(map[int]int)
collectSum(root, memo)
res := []int{}
most := 0
for key, val := range memo {
if most == val {
res = append(res, key)
} else if most < val {
most = val
res = []int{key}
}
}
return res
}

func collectSum(root *TreeNode, memo map[int]int) int {
if root == nil {
return 0
}
sum := root.Val + collectSum(root.Left, memo) + collectSum(root.Right, memo)
if v, ok := memo[sum]; ok {
memo[sum] = v + 1
} else {
memo[sum] = 1
}
return sum
}

// 解法二 求出所有和再排序
func findFrequentTreeSum1(root *TreeNode) []int {
if root == nil {
return []int{}
}
freMap, freList, reFreMap := map[int]int{}, []int{}, map[int][]int{}
findTreeSum(root, freMap)
for k, v := range freMap {
tmp := reFreMap[v]
tmp = append(tmp, k)
reFreMap[v] = tmp
}
for k := range reFreMap {
freList = append(freList, k)
}
sort.Ints(freList)
return reFreMap[freList[len(freList)-1]]
}

func findTreeSum(root *TreeNode, fre map[int]int) int {
if root == nil {
return 0
}
if root != nil && root.Left == nil && root.Right == nil {
fre[root.Val]++
return root.Val
}
val := findTreeSum(root.Left, fre) + findTreeSum(root.Right, fre) + root.Val
fre[val]++
return val
}

``````

Apr 8, 2023