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/214.5 第2层节点15、7总和22平均值22/211示例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层核心问题怎么把同一层的节点放到一起单独求和、计数再算平均两种路线BFS广度优先搜索队列层序遍历【推荐】队列一层一层往外拿。每次先记录当前队列长度当前层节点数量循环取出这一层全部节点累加总和算平均值再把子节点入队。DFS深度优先搜索递归深度遍历维护两个数组每层总和、每层节点个数。走到某个节点时根据深度在对应位置累加值计数遍历完整棵树后统一求每层均值。第二步两种解法对比✅ BFS队列优点直观一层一层处理遍历到这一层直接算出平均值不用最后统一计算面试首选。缺点需要额外队列存储节点。✅ DFS递归优点空间是递归栈不用队列适合深度不大的树。缺点要额外数组保存每层总和与数量必须遍历完整棵树之后才能计算平均值。第三步坑点费曼找易错点节点值可以是负数求和不能默认都是正数节点数量最多1e4求和要用足够大的类型Pythonint不用担心溢出除法必须是浮点数不能整数除法null节点不能入队列只处理真实节点精度答案误差小于1e-5就可以不用刻意保留很多小数位。第四步应用场景举例计算机图形学场景层次化场景树统计每一层物体的平均坐标组织架构树公司组织树每层员工平均薪资树的每一层代表职级机器学习决策树统计树每一层节点的样本均值目录树文件目录层级统计每一层文件夹的平均文件数量。解法1BFS队列层序遍历Python每行详细注释# 导入队列模块dequedeque左右弹出O(1)列表pop(0)是O(n)很慢fromcollectionsimportdequefromtypingimportList,Optional# 二叉树节点定义LeetCode内置classTreeNode:def__init__(self,val0,leftNone,rightNone):self.valval# 当前节点的值self.leftleft# 左孩子self.rightright# 右孩子classSolution:defaverageOfLevels(self,root:Optional[TreeNode])-List[float]:# 保存每层平均值的结果列表res[]# 创建队列把根节点放入队列启动BFSqdeque()q.append(root)# 队列不为空说明还有层没有遍历whileq:# 获取当前这一层一共有多少节点队列当前长度就是本层节点数level_sizelen(q)# 本层所有节点的总和初始化为0level_sum0# 循环level_size次取出本层全部节点for_inrange(level_size):# 从队列左侧弹出节点nodeq.popleft()# 当前节点值加到本层总和level_sumnode.val# 如果左孩子不为空加入队列作为下一层节点ifnode.left:q.append(node.left)# 如果右孩子不为空加入队列作为下一层节点ifnode.right:q.append(node.right)# 计算本层平均值浮点数除法avglevel_sum/level_size# 将平均值放入结果列表res.append(avg)# 返回所有层平均值returnres# 测试代码 if__name____main__:# 构建示例树 [3,9,20,null,null,15,7]rootTreeNode(3)root.leftTreeNode(9)root.rightTreeNode(20)root.right.leftTreeNode(15)root.right.rightTreeNode(7)solSolution()anssol.averageOfLevels(root)print(ans)# [3.0, 14.5, 11.0]解法2DFS深度优先递归解法Python每行详细注释fromtypingimportList,OptionalclassTreeNode:def__init__(self,val0,leftNone,rightNone):self.valval self.leftleft self.rightrightclassSolution:defaverageOfLevels(self,root:Optional[TreeNode])-List[float]:# sum_list保存每一层的总和count_list保存每一层节点个数sum_list[]count_list[]# 定义递归函数node当前节点depth当前节点所在深度defdfs(node:TreeNode,depth:int):# 递归终止条件节点为空直接返回ifnotnode:return# 如果深度等于数组长度说明第一次访问这一层# 需要给这一层初始化总和与计数ifdepthlen(sum_list):sum_list.append(node.val)count_list.append(1)else:# 不是第一次访问这一层累加值计数1sum_list[depth]node.val count_list[depth]1# 递归访问左子节点深度1dfs(node.left,depth1)# 递归访问右子节点深度1dfs(node.right,depth1)# 从根节点开始遍历根节点深度是0dfs(root,0)# 遍历sum_list计算每层平均值result[]fors,cntinzip(sum_list,count_list):result.append(s/cnt)returnresult# 测试代码 if__name____main__:# 构建树rootTreeNode(3)root.leftTreeNode(9)root.rightTreeNode(20)root.right.leftTreeNode(15)root.right.rightTreeNode(7)solSolution()print(sol.averageOfLevels(root))# [3.0,14.5,11.0]复杂度分析BFS版本时间复杂度O(n)n是节点总数每个节点入队出队各一次只遍历一遍空间复杂度O(n)最坏完全二叉树队列最多存储n/2个节点最后一层DFS版本时间复杂度O(n)每个节点访问一次空间复杂度O(h)h树高度递归栈开销最坏单边树hn费曼复盘总结本题本质是二叉树层序遍历的简单变形。BFS按层处理一层算一次均值最直观。DFS深度遍历记录每层总和和数量遍历完再算均值。面试优先写BFS不容易出错逻辑一眼看懂。