leetcode:508. 出现次数最多的子树元素和【dfs记录和】

分析

来个counter记录不同和的个数
然后dfs遍历左右求和，若为none返回0
否则返回左和+右和+本身，return前记录到count中

然后找到count的最大，并加入最大的key

ac code

# 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: TreeNode) -> List[int]:
        count = defaultdict(int)
        def dfs(root):
            if root is None:
                return 0
            
            leftSum = dfs(root.left)
            rightSum = dfs(root.right)
            thisSum = root.val + leftSum + rightSum
            count[thisSum] += 1
            return thisSum
            
        dfs(root)
        maxn = 0
        for value in count.values():
            maxn = max(maxn, value)
        
        ans = []
        for key in count.keys():
            if count[key] == maxn:
                ans.append(key)
        
        return ans

总结

经典tree dfs