出现次数最多的子树元素和-LeetCode

508. 出现次数最多的子树元素和 - Most Frequent Subtree Sum

🎯 问题描述（来源于LeetCode）

描述：
给你一个二叉树的根节点 root，找出出现次数最多的子树元素和。
子树元素和定义为：以该节点为根的子树中所有节点值之和（包括该节点本身）。
如果有多个和出现的次数相同，则按任意顺序返回这些和。

说明：

• 子树包括节点本身及其所有后代节点。
• 空树返回空列表。

示例：

• 示例 1：

输入: root = [5,2,-3]
输出: [2,-3,4]
解释: 以5为根的子树和为 5+2-3=4，以2为根的子树和为2，以-3为根的子树和为-3，每个和只出现一次，所以返回所有和。

• 示例 2：

输入: root = [5,2,-5]
输出: [2]
解释: 以5为根的子树和为 5+2-5=2，以2为根的子树和为2，以-5为根的子树和为-5，和2出现了两次，其他一次，所以返回[2]。

💻 解题思路

思路1：后序遍历 + 哈希表统计频率

算法步骤

1. 初始化：

   • 创建一个哈希表 freq，用于存储每个子树和出现的次数。
   • 设置变量 max_freq = 0，记录当前出现的最大频率。

2. 定义递归函数 dfs(node)：

   • 返回值：以 node 为根的子树元素和。
   • 递归终止：如果 node 为 None，返回 0。
   • 递归计算左右子树的和：total = node.val + dfs(node.left) + dfs(node.right)。
   • 更新哈希表：freq[total] += 1。
   • 更新最大频率：max_freq = max(max_freq, freq[total])。
   • 返回当前子树和 total。

3. 调用 dfs(root)：

   • 遍历整棵树，完成所有子树和的计算与统计。

4. 收集结果：

   • 遍历哈希表，筛选出频率等于 max_freq 的子树和，返回列表。

思路1：代码实现

# 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
from typing import List, Optional

class Solution:
    def findFrequentTreeSum(self, root: Optional[TreeNode]) -> List[int]:
        max_freq = 0
        freq = defaultdict(int)
        
        def dfs(node):
            nonlocal max_freq
            if node is None:
                return 0
            total = node.val + dfs(node.left) + dfs(node.right)
            freq[total] += 1
            max_freq = max(max_freq, freq[total])
            return total
        
        dfs(root)
        return [num for num, f in freq.items() if f == max_freq]

思路1：📊 性能分析

复杂度验证

• 时间复杂度：$O(n)$，其中 $n$ 为二叉树的节点数。每个节点恰好被访问一次，哈希表操作 $O(1)$。
• 空间复杂度：$O(n)$，最坏情况下（所有子树和均不同）哈希表存储 $n$ 个键值对，递归栈深度为树高 $O(h)$，总体为 $O(n)$。

思考

• 本题的关键是后序遍历：先计算左右子树的和，再计算当前节点子树的和，从而自然地得到每个子树的和。
• 使用 defaultdict(int) 简化计数操作，nonlocal 用于修改外层函数的可变变量 max_freq。
• 注意：返回值需要是列表，即使只有一个元素也要用列表包裹。
• 也可以使用两次遍历（先收集所有和，再统计频率），但一次遍历更优。