leetcode 508. 出现次数最多的子树元素和

题解

找出子树元素和的出现次数存入hashMap,出现次数最大值max

示例代码(go)

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
31
32
33
34
35
36
37
38
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func findFrequentTreeSum(root *TreeNode) []int {
arr := make([]int, 0)
hashMap := make(map[int]int)
max := 1
if root == nil {
return arr
}
findMap(root, hashMap, &max)
for k, v := range hashMap {
if v == max {
arr = append(arr, k)
}
}
return arr
}

func findMap(root *TreeNode, hashMap map[int]int, max *int) int {
sum := root.Val
if root.Left != nil {
sum += findMap(root.Left, hashMap, max)
}
if root.Right != nil {
sum += findMap(root.Right, hashMap, max)
}
hashMap[sum]++
if hashMap[sum] > *max {
*max = hashMap[sum]
}
return sum
}