LeetCode 题解工作台
出现次数最多的子树元素和
给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。 一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。 示例 1： 输入: root = [5,2,-3] 输出: …
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们可以使用一个哈希表 记录每个子树元素和出现的次数，然后使用深度优先搜索遍历整棵树，统计每个子树的元素和，并更新 。 最后，我们遍历 ，找到所有出现次数最多的子树元素和。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一个二叉树的根结点 root ，请返回出现次数最多的子树元素和。如果有多个元素出现的次数相同，返回所有出现次数最多的子树元素和（不限顺序）。
一个结点的 「子树元素和」 定义为以该结点为根的二叉树上所有结点的元素之和（包括结点本身）。
示例 1：
输入: root = [5,2,-3] 输出: [2,-3,4]
示例 2：
输入: root = [5,2,-5] 输出: [2]
提示:
- 节点数在
[1, 104]范围内 -105 <= Node.val <= 105
解题思路
方法一：哈希表 + DFS
我们可以使用一个哈希表 记录每个子树元素和出现的次数，然后使用深度优先搜索遍历整棵树，统计每个子树的元素和，并更新 。
最后，我们遍历 ，找到所有出现次数最多的子树元素和。
时间复杂度 ，空间复杂度 。其中 为二叉树的节点个数。
# 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: Optional[TreeNode]) -> List[int]:
def dfs(root: Optional[TreeNode]) -> int:
if root is None:
return 0
l, r = dfs(root.left), dfs(root.right)
s = l + r + root.val
cnt[s] += 1
return s
cnt = Counter()
dfs(root)
mx = max(cnt.values())
return [k for k, v in cnt.items() if v == mx]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(N) since each node is visited once during DFS. Space complexity is O(N) for the hash table storing subtree sums, plus O(H) for the recursion stack where H is tree height. |
| 空间 | O(N) |
面试官常问的追问
外企场景- question_mark
Check if the candidate correctly computes subtree sums without redundant recalculation.
- question_mark
Observe whether the hash table is updated inline during DFS for accurate frequency tracking.
- question_mark
Verify handling of ties and negative node values in the final result list.
常见陷阱
外企场景- error
Recomputing subtree sums multiple times instead of storing results in a hash table.
- error
Failing to handle multiple sums with the same maximum frequency correctly.
- error
Ignoring negative values, which can appear frequently in subtree sums and affect frequency counts.
进阶变体
外企场景- arrow_right_alt
Return the least frequent subtree sums instead of the most frequent ones.
- arrow_right_alt
Compute the sum of all subtrees whose sums fall within a specific range.
- arrow_right_alt
Adapt the problem to an N-ary tree where each node can have more than two children.