Problem
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.
問題
給你一個二叉樹的根結(jié)點，請你找出出現(xiàn)次數(shù)最多的子樹元素和滋将。一個結(jié)點的「子樹元素和」定義為以該結(jié)點為根的二叉樹上所有結(jié)點的元素之和（包括結(jié)點本身）哆窿。
你需要返回出現(xiàn)次數(shù)最多的子樹元素和肪笋。如果有多個元素出現(xiàn)的次數(shù)相同蝶念，返回所有出現(xiàn)次數(shù)最多的子樹元素和（不限順序）喘鸟。
示例 1：
輸入:
5
/ \
2 -3
返回 [2, -3, 4]橡卤，所有的值均只出現(xiàn)一次，以任意順序返回所有值榜跌。
示例 2：
輸入：
5
/ \
2 -5
返回 [2]闸天，只有 2 出現(xiàn)兩次，-5 只出現(xiàn) 1 次斜做。
提示： 假設(shè)任意子樹元素和均可以用 32 位有符號整數(shù)表示。
思路
DFS
先思考每一個節(jié)點需要做的事：該節(jié)點值與左右子樹的所有節(jié)點值相加湾揽。
同時瓤逼，要記錄次數(shù)笼吟。
再遍歷子樹元素和，取出次數(shù)最多的子樹元素和霸旗。
Python3 代碼
# 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)
# 計算子樹元素和
def dfs(node):
# 遞歸邊界
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]
