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

题目描述

给出二叉树的根,找出出现次数最多的子树元素和。一个结点的子树元素和定义为以该结点为根的二叉树上所有结点的元素之和(包括结点本身)。然后求出出现次数最多的子树元素和。如果有多个元素出现的次数相同,返回所有出现次数最多的元素(不限顺序)。

示例 1


输入:
5
/ \
2 -3
返回 [2, -3, 4],所有的值均只出现一次,以任意顺序返回所有值。

示例 2


输入:
5
/ \
2 -5
返回 [2],只有 2 出现两次,-5 只出现 1 次。

提示: 假设任意子树元素和均可以用 32 位有符号整数表示。

题解

找出子树元素和的出现次数存入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
}