力扣解题-637. 二叉树的层平均值给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10⁻⁵ 以内的答案可以被接受。示例 1输入root [3,9,20,null,null,15,7]输出[3.00000,14.50000,11.00000]解释第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。示例 2:输入root [3,9,20,15,7]输出[3.00000,14.50000,11.00000]提示树中节点数量在 [1, 10⁴] 范围内-2³¹ Node.val 2³¹ - 1Related Topics树、深度优先搜索、广度优先搜索、二叉树第一次解答解题思路核心方法广度优先搜索BFS层级遍历法利用队列实现二叉树的层级遍历逐层计算节点值的总和与数量最终求得平均值时间复杂度O(n)、空间复杂度O(n)是本题最直观、最高效的解法。核心逻辑拆解求层平均值的核心是“按层遍历逐层计算”关键在于精准区分每一层的节点初始化创建结果列表存储各层平均值队列存储待遍历节点先将根节点入队层级遍历循环队列非空时持续处理每一层记录层大小每次循环开始时队列的长度即为当前层的节点数sizequeue.size()计算层总和遍历当前层的所有节点循环size次累加节点值到总和sum并将节点的左右子节点入队为下一层遍历做准备计算平均值当前层总和除以节点数将结果加入结果列表返回结果遍历完所有层后返回存储平均值的列表。具体步骤以示例1 root[3,9,20,null,null,15,7]为例遍历层级队列初始状态层大小size累加过程层总和sum平均值结果列表0根层[3]1sum 333.0[3.0]1[9,20]2sum 9 20 292914.5[3.0, 14.5]2[15,7]2sum 15 7 222211.0[3.0, 14.5, 11.0]关键细节说明层大小固定必须在遍历当前层前记录queue.size()因为遍历过程中会将下一层节点入队队列长度会动态变化数据类型选择总和sum使用double类型避免int溢出节点值范围达2³¹多层累加易超出int范围平均值直接用sum/size计算保证精度满足题目要求10⁻⁵以内边界处理题目保证树非空无需处理rootnull的情况叶子节点的左右子节点为null不会入队不影响层遍历。性能说明时间复杂度O(n)每个节点仅入队/出队一次n为节点总数空间复杂度O(n)最坏情况队列存储一层所有节点如完全二叉树最后一层有n/2个节点优势层级遍历逻辑直观与“按层求平均值”的需求高度契合一次遍历即可完成计算无冗余操作代码简洁易理解和调试。publicListDoubleaverageOfLevels(TreeNoderoot){ListDoubleresnewArrayList();QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){intsizequeue.size();doublesum0;for(inti0;isize;i){TreeNodenodequeue.poll();sumnode.val;if(node.left!null){queue.offer(node.left);}if(node.right!null){queue.offer(node.right);}}res.add(sum/size);}returnres;}示例解答解题思路解法1深度优先搜索DFS递归法拓展思路核心方法DFS递归记录每层总和与节点数通过递归遍历二叉树用两个列表分别记录每一层的节点值总和和节点数量最后遍历列表计算平均值时间复杂度O(n)、空间复杂度O(h)h为树的高度。代码实现publicListDoubleaverageOfLevels(TreeNoderoot){// 存储每层的总和ListLongsumListnewArrayList();// 存储每层的节点数ListIntegercountListnewArrayList();// 递归遍历初始层级为0dfs(root,0,sumList,countList);// 计算平均值ListDoubleresnewArrayList();for(inti0;isumList.size();i){res.add(sumList.get(i)*1.0/countList.get(i));}returnres;}privatevoiddfs(TreeNodenode,intlevel,ListLongsumList,ListIntegercountList){if(nodenull){return;}// 首次访问该层级初始化总和和数量if(levelsumList.size()){sumList.add((long)node.val);countList.add(1);}else{// 非首次访问累加总和、增加数量sumList.set(level,sumList.get(level)node.val);countList.set(level,countList.get(level)1);}// 递归遍历左右子树层级1dfs(node.left,level1,sumList,countList);dfs(node.right,level1,sumList,countList);}核心逻辑说明递归参数level当前节点所在层级根节点为0sumList按层级存储节点值总和用Long避免溢出countList按层级存储节点数量递归处理首次访问某层级时初始化该层级的总和和数量非首次访问时累加总和、增加数量递归遍历左右子树层级1计算平均值遍历sumList和countList用“总和/数量”得到各层平均值。性能说明时间复杂度O(n)每个节点仅被访问一次空间复杂度O(h)递归栈深度等于树的高度sumList和countList的长度等于层数最多h优势无需使用队列空间复杂度在平衡树场景下优于BFSO(logn) vs O(n)适合需要同时处理层级相关的其他统计信息如总和、最大值、最小值劣势需要额外的列表存储中间结果逻辑比BFS稍复杂。解法2BFS优化版高精度处理核心方法在原BFS基础上优化数据类型使用long存储总和避免极端场景下的精度损失进一步提升结果准确性。代码实现publicListDoubleaverageOfLevels(TreeNoderoot){ListDoubleresnewArrayList();QueueTreeNodequeuenewLinkedList();queue.offer(root);while(!queue.isEmpty()){intsizequeue.size();longsum0;// 改用long存储总和避免int溢出for(inti0;isize;i){TreeNodenodequeue.poll();sumnode.val;if(node.left!null)queue.offer(node.left);if(node.right!null)queue.offer(node.right);}// 转换为double计算平均值保证精度res.add((double)sum/size);}returnres;}优化说明总和类型优化将sum从double改为long先以整数形式累加最后再转换为double计算平均值避免多次浮点累加的精度损失适用场景当节点值数量大、层级多的时候该优化能让结果更接近真实值满足题目“与实际答案相差10⁻⁵以内”的要求。总结BFS层级遍历法第一次解答O(n)时间O(n)空间逻辑直观、代码简洁是本题的工程最优解DFS递归法O(n)时间O(h)空间空间复杂度在平衡树场景下更优适合拓展层级相关的统计需求BFS高精度版O(n)时间O(n)空间优化数据类型提升极端场景下的计算精度关键技巧核心思想求层平均值的关键是“区分层级”BFS通过队列大小固定层级DFS通过层级参数标记层级溢出处理必须用long/double存储总和避免int溢出精度保证最终平均值用浮点除法计算满足题目精度要求。