难度: Medium
给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。
一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。
示例 1：
输入: root = [5,2,-3] 输出: [2,-3,4]
示例 2：
输入: root = [5,2,-5] 输出: [2]
提示:
[1, 104] 范围内-105 <= Node.val <= 105运行时间: 56 ms
内存: 19.2 MB
# 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 Counter
class Solution:
def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:
ret = []
if root is None:
return ret
tmp = []
def helper(root):
nonlocal ret
if root is None:
return 0
val = root.val
val += helper(root.left)
val += helper(root.right)
tmp.append(val)
return val
helper(root)
c = Counter(tmp).most_common()
largest = c[0][1]
for val, times in c:
if times == largest:
ret.append(val)
else:
break
return ret
该题解采用后序遍历的方式递归计算每个子树的元素和，将所有子树元素和保存到一个列表中。然后使用 Counter 统计列表中每个元素和出现的次数，找出出现次数最多的元素和，并返回所有出现次数最多的元素和组成的列表。
时间复杂度: O(nlogn)
空间复杂度: O(n)
from collections import Counter
class Solution:
def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:
ret = []
if root is None:
return ret
tmp = []
def helper(root):
nonlocal ret
if root is None:
return 0
# 计算当前节点的值
val = root.val
# 递归计算左子树的元素和
val += helper(root.left)
# 递归计算右子树的元素和
val += helper(root.right)
# 将当前子树的元素和添加到列表中
tmp.append(val)
# 返回当前子树的元素和
return val
# 递归遍历二叉树，计算所有子树的元素和
helper(root)
# 使用 Counter 统计每个子树元素和出现的次数
c = Counter(tmp).most_common()
# 获取出现次数最多的元素和的出现次数
largest = c[0][1]
# 遍历 Counter 的结果
for val, times in c:
# 如果当前元素和的出现次数等于最大次数，将其添加到结果列表中
if times == largest:
ret.append(val)
# 如果当前元素和的出现次数小于最大次数，说明后面的元素和出现次数也一定小于最大次数，直接退出循环
else:
break
return ret
在题解中，通过递归函数 `helper` 确保每个子树的元素和被正确计算。这个函数从当前节点开始，首先计算当前节点的值，然后递归地调用自身来计算左子树和右子树的元素和，并将这些值累加到当前节点的值上。递归的基准情况是遇到空节点返回0。这种后序遍历（先左后右，最后访问根）保证了每个节点在其子节点被处理完毕后才被处理，从而确保了每个子树的元素和都能被正确计算并累加。
`Counter.most_common()` 方法返回一个列表，其中元素和按照出现次数从高到低排序。因此，列表的第一个元素对（元素和，出现次数）就表示出现次数最高的元素和及其次数。这是由 `Counter` 的实现决定的，确保了最常见的元素和总是位于返回列表的第一个位置。
尽管 `Counter.most_common()` 已经提供了按频率排序的元素和，但它不提供直接的方法来筛选出所有具有最大出现次数的元素和。题解中首先从 `Counter.most_common()` 获取最大出现次数，然后使用一个循环遍历 `Counter` 的结果，比较每个元素和的出现次数与最大出现次数。这样可以有效地找出所有出现次数等于最大次数的元素和。使用循环的方法是简单且直接的，允许在确定最大次数后立即收集所有符合条件的结果，避免了进一步的不必要计算。