## Leetcode | 0508

Wonz 2021-01-20 22:19:10
leetcode

## Problem

LeetCode

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.

## problem

Power button

Give you a root node of binary tree , Please find out the subtree elements and . Of a node 「 Subtree elements and 」 It is defined as the sum of the elements of all nodes in the binary tree with the node as the root （ Including the node itself ）.

You need to return the most frequent subtree elements and . If more than one element appears the same number of times , Returns all the most frequent subtree elements and （ Unlimited order ）.

Example 1：

Input :

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

return [2, -3, 4], All values appear only once , Returns all values in any order .

Example 2： Input ：

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

return , Only 2 Twice ,-5 Only appear 1 Time .

Tips ： Suppose any subtree element sum can be used 32 Bit signed integers indicate .

## Ideas

DFS

`````` Think about what each node needs to do first ： The node value is added to all the node values of the left and right subtrees .
meanwhile , To record the number of times .
Then traverse the subtree elements and , The subtree elements and .
``````

### Python3 Code

``````# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def findFrequentTreeSum(self, root: TreeNode) -> List[int]:
import collections
res_dic = collections.defaultdict(int)
# Compute subtree elements and
def dfs(node):
# Recursive boundary
if not node:
return 0
tmp_sum = dfs(node.left) + node.val + dfs(node.right)
res_dic[tmp_sum] += 1
return tmp_sum
if not root:
return []
dfs(root)
max_cnt = 0
for cnt in res_dic.values():
max_cnt = max(max_cnt, cnt)
return [key for key, cnt in res_dic.items() if cnt == max_cnt]
``````