1.题目基本信息

1.1.题目描述

给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。

一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。

1.2.题目地址

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

2.解题方法

2.1.解题思路

深度优先搜索+哈希表

3.解题代码

python3代码

# 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

from collections import defaultdict
class Solution:
    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:
        # 思路：深度优先搜索+哈希表
        cnts = defaultdict(int)
        @cache
        def dfs(node:TreeNode) -> int:
            if node is None:
                return 0
            sum1 = node.val + dfs(node.left) + dfs(node.right)
            cnts[sum1] += 1
            return sum1
        dfs(root)
        maxVal = max(cnts.values())
        return [k for k, v in cnts.items() if v == maxVal]

4.执行结果