企业官网建设流程全解析

LeetCode 637 二叉树的层平均值（Average of Levels in Binary Tree）

难度：Easy
标签：二叉树、层序遍历BFS、深度优先DFS

题目原文

给定一个非空二叉树的根节点root，以数组的形式返回每一层节点的平均值。与实际答案相差10−510^{-5}10−5以内的答案都可以被接受。

示例1

输入：root = [3,9,20,null,null,15,7] 树结构： 3 / \ 9 20 / \ 15 7 输出：[3.0, 14.5, 11.0] 解释： 第0层：节点3，平均值=3 第1层：节点9、20，总和29，平均值 29/2=14.5 第2层：节点15、7，总和22，平均值22/2=11

示例2

输入：root = [3,9,20,15,7] 输出：[3.0,14.5,11.0]

提示

• 树节点数量范围[1,104][1, 10^4][1,104]
• 节点值范围−231≤Node.val≤231−1-2^{31} \le Node.val \le 2^{31}-1−231≤Node.val≤231−1

费曼学习法讲解破解过程（用大白话讲给小白）

第一步：看懂题目需求

一句话：从上到下，一层一层遍历二叉树，每层所有节点求平均值，按层把平均值放进列表返回。

二叉树层：

• 根节点是第0层
• 根的左右孩子是第1层
• 孩子的孩子是第2层

核心问题：怎么把同一层的节点放到一起，单独求和、计数，再算平均？
两种路线：

1. BFS广度优先搜索（队列，层序遍历）【推荐】
   队列一层一层往外拿。每次先记录当前队列长度=当前层节点数量，循环取出这一层全部节点，累加总和，算平均值，再把子节点入队。
2. DFS深度优先搜索（递归）
   深度遍历，维护两个数组：每层总和、每层节点个数。走到某个节点时，根据深度，在对应位置累加值+计数，遍历完整棵树后统一求每层均值。

第二步：两种解法对比

✅ BFS（队列）
优点：直观，一层一层处理，遍历到这一层直接算出平均值，不用最后统一计算；面试首选。
缺点：需要额外队列存储节点。

✅ DFS（递归）
优点：空间是递归栈，不用队列；适合深度不大的树。
缺点：要额外数组保存每层总和与数量，必须遍历完整棵树之后，才能计算平均值。

第三步：坑点（费曼找易错点）

1. 节点值可以是负数，求和不能默认都是正数；
2. 节点数量最多1e4，求和要用足够大的类型，Pythonint不用担心溢出；
3. 除法必须是浮点数，不能整数除法；
4. null节点不能入队列，只处理真实节点；
5. 精度：答案误差小于1e-5就可以，不用刻意保留很多小数位。

第四步：应用场景举例

1. 计算机图形学场景：层次化场景树，统计每一层物体的平均坐标；
2. 组织架构树：公司组织树，每层员工平均薪资（树的每一层代表职级）；
3. 机器学习决策树：统计树每一层节点的样本均值；
4. 目录树：文件目录层级，统计每一层文件夹的平均文件数量。

解法1：BFS队列层序遍历（Python，每行详细注释）

# 导入队列模块deque，deque左右弹出O(1)，列表pop(0)是O(n)很慢fromcollectionsimportdequefromtypingimportList,Optional# 二叉树节点定义，LeetCode内置classTreeNode:def__init__(self,val=0,left=None,right=None):self.val=val# 当前节点的值self.left=left# 左孩子self.right=right# 右孩子classSolution:defaverageOfLevels(self,root:Optional[TreeNode])->List[float]:# 保存每层平均值的结果列表res=[]# 创建队列，把根节点放入队列，启动BFSq=deque()q.append(root)# 队列不为空，说明还有层没有遍历whileq:# 获取当前这一层一共有多少节点（队列当前长度就是本层节点数）level_size=len(q)# 本层所有节点的总和，初始化为0level_sum=0# 循环level_size次：取出本层全部节点for_inrange(level_size):# 从队列左侧弹出节点node=q.popleft()# 当前节点值加到本层总和level_sum+=node.val# 如果左孩子不为空，加入队列，作为下一层节点ifnode.left:q.append(node.left)# 如果右孩子不为空，加入队列，作为下一层节点ifnode.right:q.append(node.right)# 计算本层平均值，浮点数除法avg=level_sum/level_size# 将平均值放入结果列表res.append(avg)# 返回所有层平均值returnres# ============ 测试代码 ============if__name__=="__main__":# 构建示例树： [3,9,20,null,null,15,7]root=TreeNode(3)root.left=TreeNode(9)root.right=TreeNode(20)root.right.left=TreeNode(15)root.right.right=TreeNode(7)sol=Solution()ans=sol.averageOfLevels(root)print(ans)# [3.0, 14.5, 11.0]

解法2：DFS深度优先递归解法（Python，每行详细注释）

fromtypingimportList,OptionalclassTreeNode:def__init__(self,val=0,left=None,right=None):self.val=val self.left=left self.right=rightclassSolution:defaverageOfLevels(self,root:Optional[TreeNode])->List[float]:# sum_list：保存每一层的总和；count_list：保存每一层节点个数sum_list=[]count_list=[]# 定义递归函数：node当前节点，depth当前节点所在深度defdfs(node:TreeNode,depth:int):# 递归终止条件：节点为空，直接返回ifnotnode:return# 如果深度等于数组长度：说明第一次访问这一层# 需要给这一层初始化总和与计数ifdepth==len(sum_list):sum_list.append(node.val)count_list.append(1)else:# 不是第一次访问这一层：累加值，计数+1sum_list[depth]+=node.val count_list[depth]+=1# 递归访问左子节点，深度+1dfs(node.left,depth+1)# 递归访问右子节点，深度+1dfs(node.right,depth+1)# 从根节点开始遍历，根节点深度是0dfs(root,0)# 遍历sum_list，计算每层平均值result=[]fors,cntinzip(sum_list,count_list):result.append(s/cnt)returnresult# ============ 测试代码 ============if__name__=="__main__":# 构建树root=TreeNode(3)root.left=TreeNode(9)root.right=TreeNode(20)root.right.left=TreeNode(15)root.right.right=TreeNode(7)sol=Solution()print(sol.averageOfLevels(root))# [3.0,14.5,11.0]

复杂度分析

BFS版本

• 时间复杂度：O(n)，n是节点总数，每个节点入队出队各一次，只遍历一遍
• 空间复杂度：O(n)，最坏完全二叉树，队列最多存储n/2个节点（最后一层）

DFS版本

• 时间复杂度：O(n)，每个节点访问一次
• 空间复杂度：O(h)，h树高度，递归栈开销；最坏单边树h=n

费曼复盘总结

本题本质是二叉树层序遍历的简单变形。
BFS：按层处理，一层算一次均值，最直观。
DFS：深度遍历，记录每层总和和数量，遍历完再算均值。
面试优先写BFS，不容易出错，逻辑一眼看懂。