LeetCode 题解工作台
统计值等于子树平均值的节点数
给你一棵二叉树的根节点 root ，找出并返回满足要求的节点数，要求节点的值等于其 子树 中值的 平均值 。 注意： n 个元素的平均值可以由 n 个元素 求和 然后再除以 n ，并 向下舍入 到最近的整数。 root 的 子树 由 root 和它的所有后代组成。 示例 1： 输入： root = …
3
题型
5
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们设计一个函数 ，它的作用是计算以当前节点为根的子树的和以及节点个数。 函数 的执行过程如下：
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一棵二叉树的根节点 root ，找出并返回满足要求的节点数，要求节点的值等于其 子树 中值的 平均值 。
注意：
n个元素的平均值可以由n个元素 求和 然后再除以n，并 向下舍入 到最近的整数。root的 子树 由root和它的所有后代组成。
示例 1：
输入：root = [4,8,5,0,1,null,6] 输出：5 解释： 对值为 4 的节点：子树的平均值 (4 + 8 + 5 + 0 + 1 + 6) / 6 = 24 / 6 = 4 。 对值为 5 的节点：子树的平均值 (5 + 6) / 2 = 11 / 2 = 5 。 对值为 0 的节点：子树的平均值 0 / 1 = 0 。 对值为 1 的节点：子树的平均值 1 / 1 = 1 。 对值为 6 的节点：子树的平均值 6 / 1 = 6 。
示例 2：
输入：root = [1] 输出：1 解释：对值为 1 的节点：子树的平均值 1 / 1 = 1。
提示：
- 树中节点数目在范围
[1, 1000]内 0 <= Node.val <= 1000
解题思路
方法一：DFS
我们设计一个函数 ，它的作用是计算以当前节点为根的子树的和以及节点个数。
函数 的执行过程如下：
- 如果当前节点为空，返回 。
- 否则，我们递归计算左右子树的和以及节点个数，分别记为 和 。那么，以当前节点为根的子树的和 和节点个数 分别为 和 。如果 ，则说明当前节点满足题目要求，我们将答案 自增 。
- 最后，函数 返回 和 。
我们初始化答案 为 ，然后调用 函数，最后返回答案 。
时间复杂度 ，空间复杂度 。其中 表示二叉树的节点个数。
class Solution:
def averageOfSubtree(self, root: TreeNode) -> int:
def dfs(root) -> tuple:
if not root:
return 0, 0
ls, ln = dfs(root.left)
rs, rn = dfs(root.right)
s = ls + rs + root.val
n = ln + rn + 1
nonlocal ans
ans += int(s // n == root.val)
return s, n
ans = 0
dfs(root)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for knowledge of depth-first search traversal.
- question_mark
Ensure the candidate can track both sum and count during traversal.
- question_mark
Check for clarity in recursive state maintenance during traversal.
常见陷阱
外企场景- error
Failing to account for the correct subtree sum and count for each node.
- error
Incorrectly updating the result when a node's value doesn't match the average.
- error
Not handling edge cases such as a single-node tree properly.
进阶变体
外企场景- arrow_right_alt
Different binary tree traversal methods such as BFS instead of DFS.
- arrow_right_alt
Handling trees with negative or very large node values.
- arrow_right_alt
Optimizing space complexity for larger trees or restricted environments.