力扣解题-637. 二叉树的层平均值

力扣解题-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³¹ - 1

Related Topics
树、深度优先搜索、广度优先搜索、二叉树

第一次解答

解题思路

核心方法：广度优先搜索（BFS）层级遍历法，利用队列实现二叉树的层级遍历，逐层计算节点值的总和与数量，最终求得平均值，时间复杂度O(n)、空间复杂度O(n)，是本题最直观、最高效的解法。

核心逻辑拆解

求层平均值的核心是“按层遍历+逐层计算”，关键在于精准区分每一层的节点：

1. 初始化：创建结果列表存储各层平均值，队列存储待遍历节点，先将根节点入队；
2. 层级遍历循环：队列非空时，持续处理每一层：
   • 记录层大小：每次循环开始时，队列的长度即为当前层的节点数（size=queue.size()）；
   • 计算层总和：遍历当前层的所有节点（循环size次），累加节点值到总和sum，并将节点的左右子节点入队（为下一层遍历做准备）；
   • 计算平均值：当前层总和除以节点数，将结果加入结果列表；
3. 返回结果：遍历完所有层后，返回存储平均值的列表。

具体步骤（以示例1 root=[3,9,20,null,null,15,7]为例）

关键细节说明

• 层大小固定：必须在遍历当前层前记录queue.size()，因为遍历过程中会将下一层节点入队，队列长度会动态变化；
• 数据类型选择：
  • 总和sum使用double类型，避免int溢出（节点值范围达2³¹，多层累加易超出int范围）；
  • 平均值直接用sum/size计算，保证精度满足题目要求（10⁻⁵以内）；
• 边界处理：题目保证树非空，无需处理root=null的情况；叶子节点的左右子节点为null，不会入队，不影响层遍历。

性能说明

• 时间复杂度：O(n)（每个节点仅入队/出队一次，n为节点总数）；
• 空间复杂度：O(n)（最坏情况队列存储一层所有节点，如完全二叉树最后一层有n/2个节点）；
• 优势：
  1. 层级遍历逻辑直观，与“按层求平均值”的需求高度契合；
  2. 一次遍历即可完成计算，无冗余操作；
  3. 代码简洁，易理解和调试。

publicList<Double>averageOfLevels(TreeNoderoot){List<Double>res=newArrayList<>();Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){intsize=queue.size();doublesum=0;for(inti=0;i<size;i++){TreeNodenode=queue.poll();sum+=node.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为树的高度）。

代码实现

publicList<Double>averageOfLevels(TreeNoderoot){// 存储每层的总和List<Long>sumList=newArrayList<>();// 存储每层的节点数List<Integer>countList=newArrayList<>();// 递归遍历，初始层级为0dfs(root,0,sumList,countList);// 计算平均值List<Double>res=newArrayList<>();for(inti=0;i<sumList.size();i++){res.add(sumList.get(i)*1.0/countList.get(i));}returnres;}privatevoiddfs(TreeNodenode,intlevel,List<Long>sumList,List<Integer>countList){if(node==null){return;}// 首次访问该层级，初始化总和和数量if(level==sumList.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,level+1,sumList,countList);dfs(node.right,level+1,sumList,countList);}

核心逻辑说明

1. 递归参数：
   • level：当前节点所在层级（根节点为0）；
   • sumList：按层级存储节点值总和（用Long避免溢出）；
   • countList：按层级存储节点数量；
2. 递归处理：
   • 首次访问某层级时，初始化该层级的总和和数量；
   • 非首次访问时，累加总和、增加数量；
   • 递归遍历左右子树，层级+1；
3. 计算平均值：遍历sumList和countList，用“总和/数量”得到各层平均值。

性能说明

• 时间复杂度：O(n)（每个节点仅被访问一次）；
• 空间复杂度：O(h)（递归栈深度等于树的高度，sumList和countList的长度等于层数，最多h）；
• 优势：
  1. 无需使用队列，空间复杂度在平衡树场景下优于BFS（O(logn) vs O(n)）；
  2. 适合需要同时处理层级相关的其他统计信息（如总和、最大值、最小值）；
• 劣势：需要额外的列表存储中间结果，逻辑比BFS稍复杂。

解法2：BFS优化版（高精度处理）

核心方法：在原BFS基础上优化数据类型，使用long存储总和，避免极端场景下的精度损失，进一步提升结果准确性。

代码实现

publicList<Double>averageOfLevels(TreeNoderoot){List<Double>res=newArrayList<>();Queue<TreeNode>queue=newLinkedList<>();queue.offer(root);while(!queue.isEmpty()){intsize=queue.size();longsum=0;// 改用long存储总和，避免int溢出for(inti=0;i<size;i++){TreeNodenode=queue.poll();sum+=node.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⁻⁵以内”的要求。

总结

1. BFS层级遍历法（第一次解答）：O(n)时间+O(n)空间，逻辑直观、代码简洁，是本题的工程最优解；
2. DFS递归法：O(n)时间+O(h)空间，空间复杂度在平衡树场景下更优，适合拓展层级相关的统计需求；
3. BFS高精度版：O(n)时间+O(n)空间，优化数据类型，提升极端场景下的计算精度；
4. 关键技巧：
   • 核心思想：求层平均值的关键是“区分层级”，BFS通过队列大小固定层级，DFS通过层级参数标记层级；
   • 溢出处理：必须用long/double存储总和，避免int溢出；
   • 精度保证：最终平均值用浮点除法计算，满足题目精度要求。