二叉树的层平均值怎么求？BFS双循环模板与DFS备选写法

1. 读懂题目在问什么：层平均值到底在考什么

1.1 题目输入输出与关键约束

先把手上的题目完整还原一遍：给定一棵二叉树，返回一个列表，列表里的每一项是对应层的节点值的平均值。比如一棵三层的树，第一层只有根节点，那结果列表的第一个数就是根节点的值除以1；第二层有两个节点，就把这两个节点的值加起来除以2，依此类推。

力扣给的函数签名大体长这样：

public List<Double> averageOfLevels(TreeNode root)

输入是根节点 root，输出是List<Double>。这里有个容易被忽略的约束：空树怎么办？题目本身没有单独强调，但按照二叉树题目的通用约定，空树返回一个空列表，而不是null，也不是抛异常。这个约定在力扣的测试用例里是默认成立的，很多人在现场写代码时忽略了这一行，结果测试用例有一个空树就直接红了一大片。

另一个隐蔽约束是节点的值域。二叉树节点的val是Integer范围内的整数，也就是说可能是负数，也可能非常大。这个细节在我们后来选sum的数据类型时有决定性影响，后面专门讲。

1.2 为什么“层”这个字决定了算法选型

这道题名字里最值钱的字是“层”。二叉树相关的题目，一旦出现“层”这个字，基本就是在暗示你要围绕树的层级关系做文章。层序遍历（BFS，广度优先搜索）是天然按层展开的：从根节点出发，先处理完第一层，再处理第二层，再第三层，逐层推进。这个顺序恰好就是题目要求的输出顺序。

有同学会想：我用深度优先搜索（DFS）把每一层的节点值收集起来，汇总到List<List<Integer>>或类似结构里，最后再遍历一次求平均值，不就完了吗？确实可以，而且这是一种合法的思路，但它在思路上绕了一个弯：DFS 是“先一头扎到底，再回来扎另一条分支”，你需要在递归时额外记录当前深度。而 BFS 根本不需要记录深度，因为队列天然地帮你把同一层的节点放在了一起。

我刷题时的判断标准很简单：题目要求按层输出、按层统计、按层比较的，优先想 BFS。如果不是按层，而是按路径、按子树、按节点关系，再考虑 DFS。这不是什么高深理论，就是一个经验法则，但它能帮你省掉大量在两种遍历方式之间来回切换的纠结时间。

2. 双循环BFS：二叉树层序平均值的标准解法

2.1 代码骨架：外层控层、内层控点

BFS 层序遍历的标准写法是用一个队列，配合一个“双层循环”结构。我先把完整代码放出来，然后一行一行拆开讲。

class Solution { public List<Double> averageOfLevels(TreeNode root) { List<Double> res = new ArrayList<>(); if (root == null) { return res; } Queue<TreeNode> queue = new LinkedList<>(); queue.offer(root); while (!queue.isEmpty()) { int size = queue.size(); double sum = 0; for (int i = 0; i < size; i++) { TreeNode node = 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); } return res; } }

这个结构非常经典，我愿称之为“层遍历双循环模板”：外层while控制“还有没有下一层”，内层for控制“把当前层这一批节点全部处理完”。

外层每循环一次，就代表处理完一层。外层进入时，队列里存放的恰好是当前层的全部节点，一个不多一个不少。这个性质来自 BFS 的入队顺序：从根开始，每处理一个节点，就把它的左右孩子放到队尾。等当前层所有节点都从队头弹出后，队尾积压的正好就是下一层的所有节点。

内层循环的size变量是在进入for之前就用queue.size()固定下来的。这一点极其关键，很多人在这里踩过坑，下面单独展开。

2.2 为什么必须先缓存size，不能直接用queue.size()

这是个高频翻车点。有同学会把内层循环写错，比如：

for (int i = 0; i < queue.size(); i++) { TreeNode node = queue.poll(); // ... }

看起来好像差不多，其实完全不是一回事。queue.size()在循环过程中是动态变化的，每poll()一次，队列长度就减一；每offer()一个子节点，队列长度又加一。

假设当前层有 8 个节点，每个节点都有一个左孩子。你进入循环时queue.size()是 8，第一次poll()后长度变成 7，紧接着offer()一个孩子又变成 8；第二次循环判断i < queue.size()时，i 是 1，queue.size() 还是 8；等你处理完这一层，i 已经变成 8，而队列长度也还是 8，于是循环继续——你实际上把下一层的节点也当成当前层处理了。最后算出来的平均值完全错乱。

正确做法就是用变量size把进入这一层时的队列长度固定下来。这个技巧不只在求平均值这道题里有用，凡是需要“逐层处理”的 BFS 变体题，比如求层最大值、层节点个数、层的右视图，全都统一用这个结构。

顺便说一下为什么这里用Queue<TreeNode> queue = new LinkedList<>()而不是ArrayList。在 Java 里，LinkedList实现了Queue接口，poll 和 offer 都是 O(1) 操作。你要是非用ArrayList当队列，就涉及到头部删除时的元素搬移，复杂度变成 O(n)，在树节点很多时会明显变慢。刷题时用最顺手的数据结构做最合适的事。

2.3 复杂度与边界情况

时间复杂度和空间复杂度都要明确说出来，面试和写复盘笔记都需要。

时间复杂度是 O(n)，n 是二叉树节点总数。每个节点恰好进入队列一次、出队一次，内层处理每个节点时只做常数次操作。

空间复杂度是 O(m)，m 是二叉树中某一层的最大节点数，也就是队列在某一时刻的最大长度。别把空间复杂度简单写成一个 O(n) 就完事了。最坏情况下，一棵“满二叉树”的最后一层节点数大约是 n/2，所以 m ≈ n/2，因此空间复杂度可以说 O(n)，但准确地说，它取决于树的最大层宽度，而非树高。

边界情况主要有三种：

• 空树：直接返回空列表。
• 单节点树：queue.size()为 1，内层循环只执行一次，sum / size就是这个节点值本身，结果正确。
• 节点值含有负数：sum可能累加出负值，除以size后得到负平均值，完全没问题，因为List<Double>本来就能存负数。

这三种情况我在实际跑用例时都遇到过，尤其是空树那条，越是觉得“题目不可能给空树”就越容易漏判。我现在的习惯是：拿到任何二叉树题目，先写空树判断，再想主逻辑。这是一个零成本的好习惯。

3. 代码落地时的两个隐蔽坑：溢出与精度

3.1 sum的类型选择：int溢出场景复现

我第一次写这道题的时候，sum用的是int，觉得节点值总和最多也就是几万几百万，int 完全放得下。后来跑一个深度较大的测试用例才发现不对。

力扣这道题对二叉树的层数没有做严格限制，最坏情况下可以构造一棵链状树（每个节点只有一个孩子），深度可以达到几千甚至更多。但如果只是链状，每层只有一个节点，单个节点值就算到 int 上限 2147483647，累加总和也不会溢出，因为每次都只加一个节点。

真正危险的是满二叉树这种情况。假设一棵深度为 10 的满二叉树，最后一层有 512 个节点，每个节点值为 10^9 量级，这一层的 sum 就是 512 * 10^9 = 5.12 * 10^11，早就超过 int 上限了。在力扣实际测试用例里，节点值可以高达 10^9 甚至更大，层级深度也可以做到十几层，int 溢出是真实会发生的事情，而不是理论上的杞人忧天。

int溢出后会发生什么？Java 里整数溢出不会抛异常，而是静默地变成负数或错误的正数。比如 2147483647 + 1 会得到 -2147483648，你拿这个负数去求平均，答案自然全错了。这种错误极其隐蔽，因为代码本身不报错，逻辑看起来也通，但就是输出不对。

方案有两个：

1. 把sum声明为long，保证整数累加不溢出。
2. 把sum声明为double，用浮点累加。

我用的是double，原因有两个。第一，最终结果要求返回List<Double>，用double做累加最后一步直接sum / size就是 Double 类型，不需要再转身。第二，对于树宽很大的用例，double尾数部分有 52 位，大约能精确表示 4.5 * 10^15 以内的整数，远大于 int 表达范围，实测不会出现精度不够导致平均值错误的问题。

注意：如果你用的是 Python，list 里放 float，完全不用操心这个问题。但 Java 里int溢出是个非常现实的坑，别问我为什么知道，都是泪。

同理，下面这段 DFS 的解法里，sums 列表也要声明成List<Double>，千万不能写成List<Integer>，否则一样溢出。

3.2 空指针与单节点特判

还有一个低级但常见的错误：在往队列里加入子节点时不判空。

if (node.left != null) { queue.offer(node.left); } if (node.right != null) { queue.offer(node.right); }

这两行看起来很简单，但如果省略判断，直接把node.left丢进队列：

queue.offer(node.left); queue.offer(node.right);

那么叶子节点（left 和 right 都是 null）就会把 null 送入队列。下一次外层循环取出一个 null，再执行node.val就会抛NullPointerException。

这个错误初期很容易犯，因为你处理 root 时 root 不为 null，但 root 并不代表它的左右孩子也不为 null。树结构是递归的，每一层都要做空判断，不能只在入口判断一次。

经验之谈：所有 BFS 层序遍历题，入口判断根为空 + 入队时判断子节点为空，这两个点养成肌肉记忆，能省掉至少一半的调试时间。

4. 面试官追问：DFS也能算层平均值吗

4.1 DFS带深度标记的替代写法

BFS 是这道题的最优解，但面试官经常在你说完解法之后追问一句：“如果不用 BFS，你还能怎么解？”这时候如果你说“DFS 不行”，就露怯了。DFS 完全能做，只是写法不同。

思路是：DFS 在递归时把当前深度传下去，用一个列表收集每一层的节点值总和，用另一个列表收集每一层的节点个数。遍历完整棵树后，两个列表按索引相除，就是每一层的平均值。

class Solution { private List<Double> sums = new ArrayList<>(); private List<Integer> counts = new ArrayList<>(); public List<Double> averageOfLevels(TreeNode root) { dfs(root, 0); List<Double> res = new ArrayList<>(); for (int i = 0; i < sums.size(); i++) { res.add(sums.get(i) / counts.get(i)); } return res; } private void dfs(TreeNode node, int depth) { if (node == null) { return; } if (depth == sums.size()) { sums.add(0.0); counts.add(0); } sums.set(depth, sums.get(depth) + node.val); counts.set(depth, counts.get(depth) + 1); dfs(node.left, depth + 1); dfs(node.right, depth + 1); } }

这段代码的核心是if (depth == sums.size())这个判断。在递归过程中，第一次到达某一深度时，sums 和 counts 的规模刚好等于 depth，此时给这两个列表追加一个初始元素。之后再次访问同一深度时，depth 一定小于 sums.size()，就直接按索引累加。

对比一下两种方法：

两种方法的时间复杂度都是 O(n)。空间上，BFS 的空间取决于树的“宽度”，DFS 的空间取决于树的“高度”。对于一棵满二叉树，树高是 log n，所以 DFS 的空间反而更小；对于一棵链状树，树高是 n，DFS 会递归 n 层，有爆栈的风险，而 BFS 每层只有一个节点，队列长度始终为 1，反而稳。没有一种遍历方式在所有形态的树上都优于另一种。

4.2 BFS和DFS的选择依据

从实践角度说，我会这样选：

• 题目要求按层输出、按层统计、按层比较，默认用 BFS。
• 题目要求找路径（比如根到叶子节点的和），或者要求按某种前序/中序/后序的顺序处理，默认用 DFS。
• 如果题目明确给了“树可能会非常深，比如 10^5 层”，不要再写递归 DFS，优先想 BFS，因为递归深度过大会导致栈溢出。
• 如果题目要求用 O(log n) 的额外空间，比如某些平衡二叉树场景，DFS（递归实现）的空间复杂度是 O(h)，满二叉树时 h = log n，可以考虑；但如果是链状二叉树，DFS 空间会退化到 O(n)，这时 BFS 反而空间更优。

对于本题而言，BFS 是更自然、更好解释、也更容易实现的选择。但能在面试时补出一段 DFS 写法，并能说清楚两种遍历在空间复杂度上的差异，才算是真正吃透了这道题。

5. 从637延伸出去：一套层遍历通用套路

5.1 层最大值、层求和、层内反转变体

力扣的二叉树题目有很多都是同一套“层遍历”模子的换皮，刷多了你会发现它们用的都是同一个双循环结构。

• 求二叉树每层的最大值：内层循环里不再累加 sum，而是维护一个max，每次Math.max(max, node.val)。
• 求二叉树每层的平均值：就是本题。
• 求二叉树每层的节点个数：内层循环用一个count变量自增。
• 二叉树的层序遍历（输出成一个List<List<Integer>>）：内层循环里把节点值加入一个临时 list，结束后再统一加入结果。
• 二叉树的锯齿形层序遍历：在层序遍历模板上，用一个boolean变量记录当前层是否反转，偶数层就Collections.reverse(temp)。
• 二叉树的右视图：每一层处理完后，取出最后一个节点的值加入结果。

这些题的共同点是：永远有一层while，永远有一层for，永远在for开始前用一个变量固定queue.size()。我把这个套路总结成一个四步口诀：

1. 初始化队列，把根节点放进去。
2. 外层while (!queue.isEmpty())表示还有层没处理。
3. 内层for循环固定次数，次数等于当前层节点数。
4. 在for内部做当前层需要的统计，并把下一层节点入队。

这个口诀适用于至少七八道力扣二叉树题。每道题只是内层统计方式不一样，骨架完全一致。

5.2 如何把这道题的框架套到其他题目上

拿层平均值这道题举例，它和“找每层最大节点”唯一的区别就在内层循环里的那两三行代码。我实际刷题时，遇到新的层相关题目，会先写一个完整的“空 BFS 模板”，然后往模板里填这道题特有的逻辑：

while (!queue.isEmpty()) { int size = queue.size(); // TODO: 在这里初始化本层的统计变量 for (int i = 0; i < size; i++) { TreeNode node = queue.poll(); // TODO: 在这里做本层节点的统计 if (node.left != null) queue.offer(node.left); if (node.right != null) queue.offer(node.right); } // TODO: 在这里把本层统计结果加入答案 }

这个模板我用了很久，确实提升了刷题效率。它的本质是把“如何遍历树”这个部分固定下来，把精力集中在“当前层要做什么统计”这个可变部分。

用这个模板解层最大值题，只需要在TODO处填三块：初始化int max = Integer.MIN_VALUE;，内层循环里max = Math.max(max, node.val);，循环结束后res.add(max);。几乎不需要改其他代码。

我之前带过一个同学，只练习了层序遍历这一道题，然后用这个模板一口气解决了四五道层相关的中等难度题，说明这个套路确实是可复制的。

5.3 一道刷题心法：先问自己要什么，再选遍历方式

谈一点个人体会。我刷二叉树题目时最常问自己的问题是：我要按“层”拿数据，还是按“路径”拿数据？这个问题的答案基本决定了用什么遍历。

“层”相关的关键词包括：层平均值、层最大值、层最小值、层右视图、层序序列化、之字形遍历。看到这些，BFS 是第一候选。

“路径”相关的关键词包括：根到叶子节点和、最大路径和、最近公共祖先、二叉树直径、翻转等价。这些题里，DFS 往往更自然，因为你需要在递归中携带路径信息。

如果一道题既和层有关，又可能深度非常大，BFS 依然能打，因为队列的容量只取决于最大层宽，而不取决于总深度。反过来，DFS 递归在深度过大时会有栈溢出风险。

“637.二叉树的层平均值”这道题本身不难，但我建议你把它当成一个“模板锚点题”。什么意思呢？就是把这道题吃透，把双循环 BFS 的骨架背下来，再把 DFS 带深度参数的写法也理解了，那么你后面刷任何层相关题目，都是在往这个已经建好的骨架上加肉。我自己的刷题路径就是这样：先用简单题建立模板，再用中等题在模板上做替换练习，最后见到新题第一时间就能识别出它属于哪个模板的变体。这种“以模板带题”的方式，比单纯按难度刷题要扎实得多。