LeetCode 题解工作台
二叉树的层平均值
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10 -5 以内的答案可以被接受。 示例 1： 输入： root = [3,9,20,null,null,15,7] 输出： [3.00000,14.50000,11.00000] 解释： 第 0 层的平均…
4
题型
6
代码语言
3
相关题
当前训练重点
简单 · 二分·树·traversal
答案摘要
我们可以使用广度优先搜索的方法，遍历每一层的节点，计算每一层的平均值。 具体地，我们定义一个队列 ，初始时将根节点加入队列。每次将队列中的所有节点取出，计算这些节点的平均值，加入答案数组中，并将这些节点的子节点加入队列。重复这一过程，直到队列为空。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[3.00000,14.50000,11.00000] 解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。 因此返回 [3, 14.5, 11] 。
示例 2:
输入：root = [3,9,20,15,7] 输出：[3.00000,14.50000,11.00000]
提示：
- 树中节点数量在
[1, 104]范围内 -231 <= Node.val <= 231 - 1
解题思路
方法一：BFS
我们可以使用广度优先搜索的方法，遍历每一层的节点，计算每一层的平均值。
具体地，我们定义一个队列 ，初始时将根节点加入队列。每次将队列中的所有节点取出，计算这些节点的平均值，加入答案数组中，并将这些节点的子节点加入队列。重复这一过程，直到队列为空。
时间复杂度 ，空间复杂度 。其中 是二叉树的节点个数。
# 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 averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
q = deque([root])
ans = []
while q:
s, n = 0, len(q)
for _ in range(n):
root = q.popleft()
s += root.val
if root.left:
q.append(root.left)
if root.right:
q.append(root.right)
ans.append(s / n)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Can the candidate explain why BFS or DFS is chosen for this problem?
- question_mark
Does the candidate account for variations in the tree structure, such as depth and width?
- question_mark
Can the candidate efficiently track state without excessive memory use?
常见陷阱
外企场景- error
Forgetting to handle cases with missing child nodes (null) during traversal.
- error
Incorrectly calculating the average by not properly tracking node count or sum.
- error
Misunderstanding tree structure, leading to wrong assumptions about level depth or node placement.
进阶变体
外企场景- arrow_right_alt
Modify the problem to return the sum instead of the average for each level.
- arrow_right_alt
Adapt the problem to handle non-binary trees or other tree variations.
- arrow_right_alt
Consider cases where all node values are the same, and optimize the algorithm accordingly.