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

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

https://leetcode-cn.com/problems/most-frequent-subtree-sum/

解法一：前序+hash

前序遍历，每次递归求和并记录在hash，key为和，值为次数

遍历hash，找出现最多的次数most

再遍历hash，将次数为most的key输出

# 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]:
        self.hash = {}    #全局hash
        self.helper(root)    #辅助函数
        most = 0    #出现最多的次数
        for key in self.hash:
            most = max(most, self.hash[key])
        res = []    #输出
        for key in self.hash:
            if self.hash[key] == most:
                res.append(key)
        return res
    
    def helper(self, root):
        if not root:
            return 0
        sum = root.val
        #递归求左右子树和
        sum += self.helper(root.left)
        sum += self.helper(root.right)
        #得到一个子树和，写入
        if sum not in self.hash:
            self.hash[sum] = 0
        self.hash[sum] += 1
        return sum