# LeetCode: 508. Most Frequent Subtree Sum

Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

## 题目¶

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 , 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.

## 解法¶

```# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def findFrequentTreeSum(self, root):
# 统计各个子树的 sum 和的次数
self._sum_count = {}
# 最常使用的和的次数，最少出现一次
self._most_frequent_count = 1
# 最常使用的和的值，应对不止一个结果的情况
self._most_frequent_count_values = []

self._sum(root)

return self._most_frequent_count_values

def _sum(self, root):
if root is None:
return 0

val = root.val
left = self._sum(root.left)
right = self._sum(root.right)

sum_value = val + left + right
# 收集子树和并更新 most frequent sum 结果
self._update_frequent_sum_count(sum_value)

return sum_value

def _update_frequent_sum_count(self, sum_value):
if sum_value in self._sum_count:
self._sum_count[sum_value] += 1
else:
self._sum_count[sum_value] = 1

count = self._sum_count[sum_value]
# 收集相同次数的 sum value
if count == self._most_frequent_count:
self._most_frequent_count_values.append(sum_value)
elif count > self._most_frequent_count:
# most frequent 的宝座换人
self._most_frequent_count = count
self._most_frequent_count_values = [sum_value]
```