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

1. 读懂题目在问什么层平均值到底在考什么1.1 题目输入输出与关键约束先把手上的题目完整还原一遍给定一棵二叉树返回一个列表列表里的每一项是对应层的节点值的平均值。比如一棵三层的树第一层只有根节点那结果列表的第一个数就是根节点的值除以1第二层有两个节点就把这两个节点的值加起来除以2依此类推。力扣给的函数签名大体长这样public ListDouble averageOfLevels(TreeNode root)输入是根节点 root输出是ListDouble。这里有个容易被忽略的约束空树怎么办题目本身没有单独强调但按照二叉树题目的通用约定空树返回一个空列表而不是null也不是抛异常。这个约定在力扣的测试用例里是默认成立的很多人在现场写代码时忽略了这一行结果测试用例有一个空树就直接红了一大片。另一个隐蔽约束是节点的值域。二叉树节点的val是Integer范围内的整数也就是说可能是负数也可能非常大。这个细节在我们后来选sum的数据类型时有决定性影响后面专门讲。1.2 为什么“层”这个字决定了算法选型这道题名字里最值钱的字是“层”。二叉树相关的题目一旦出现“层”这个字基本就是在暗示你要围绕树的层级关系做文章。层序遍历BFS广度优先搜索是天然按层展开的从根节点出发先处理完第一层再处理第二层再第三层逐层推进。这个顺序恰好就是题目要求的输出顺序。有同学会想我用深度优先搜索DFS把每一层的节点值收集起来汇总到ListListInteger或类似结构里最后再遍历一次求平均值不就完了吗确实可以而且这是一种合法的思路但它在思路上绕了一个弯DFS 是“先一头扎到底再回来扎另一条分支”你需要在递归时额外记录当前深度。而 BFS 根本不需要记录深度因为队列天然地帮你把同一层的节点放在了一起。我刷题时的判断标准很简单题目要求按层输出、按层统计、按层比较的优先想 BFS。如果不是按层而是按路径、按子树、按节点关系再考虑 DFS。这不是什么高深理论就是一个经验法则但它能帮你省掉大量在两种遍历方式之间来回切换的纠结时间。2. 双循环BFS二叉树层序平均值的标准解法2.1 代码骨架外层控层、内层控点BFS 层序遍历的标准写法是用一个队列配合一个“双层循环”结构。我先把完整代码放出来然后一行一行拆开讲。class Solution { public ListDouble averageOfLevels(TreeNode root) { ListDouble res new ArrayList(); if (root null) { return res; } QueueTreeNode 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 是 1queue.size() 还是 8等你处理完这一层i 已经变成 8而队列长度也还是 8于是循环继续——你实际上把下一层的节点也当成当前层处理了。最后算出来的平均值完全错乱。正确做法就是用变量size把进入这一层时的队列长度固定下来。这个技巧不只在求平均值这道题里有用凡是需要“逐层处理”的 BFS 变体题比如求层最大值、层节点个数、层的右视图全都统一用这个结构。顺便说一下为什么这里用QueueTreeNode 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后得到负平均值完全没问题因为ListDouble本来就能存负数。这三种情况我在实际跑用例时都遇到过尤其是空树那条越是觉得“题目不可能给空树”就越容易漏判。我现在的习惯是拿到任何二叉树题目先写空树判断再想主逻辑。这是一个零成本的好习惯。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你拿这个负数去求平均答案自然全错了。这种错误极其隐蔽因为代码本身不报错逻辑看起来也通但就是输出不对。方案有两个把sum声明为long保证整数累加不溢出。把sum声明为double用浮点累加。我用的是double原因有两个。第一最终结果要求返回ListDouble用double做累加最后一步直接sum / size就是 Double 类型不需要再转身。第二对于树宽很大的用例double尾数部分有 52 位大约能精确表示 4.5 * 10^15 以内的整数远大于 int 表达范围实测不会出现精度不够导致平均值错误的问题。注意如果你用的是 Pythonlist 里放 float完全不用操心这个问题。但 Java 里int溢出是个非常现实的坑别问我为什么知道都是泪。同理下面这段 DFS 的解法里sums 列表也要声明成ListDouble千万不能写成ListInteger否则一样溢出。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 ListDouble sums new ArrayList(); private ListInteger counts new ArrayList(); public ListDouble averageOfLevels(TreeNode root) { dfs(root, 0); ListDouble 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()就直接按索引累加。对比一下两种方法对比维度BFS 双循环DFS 深度记录是否需要记录深度不需要队列天然分层需要显式传 depth 参数空间复杂度主要消耗队列取决于最大层宽递归栈取决于树高代码可读性结构直观容易套模板需要额外理解“先扩展再累加”的时机应用场景层相关题目首选面试追问时的加分写法两种方法的时间复杂度都是 O(n)。空间上BFS 的空间取决于树的“宽度”DFS 的空间取决于树的“高度”。对于一棵满二叉树树高是 log n所以 DFS 的空间反而更小对于一棵链状树树高是 nDFS 会递归 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变量自增。二叉树的层序遍历输出成一个ListListInteger内层循环里把节点值加入一个临时 list结束后再统一加入结果。二叉树的锯齿形层序遍历在层序遍历模板上用一个boolean变量记录当前层是否反转偶数层就Collections.reverse(temp)。二叉树的右视图每一层处理完后取出最后一个节点的值加入结果。这些题的共同点是永远有一层while永远有一层for永远在for开始前用一个变量固定queue.size()。我把这个套路总结成一个四步口诀初始化队列把根节点放进去。外层while (!queue.isEmpty())表示还有层没处理。内层for循环固定次数次数等于当前层节点数。在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 带深度参数的写法也理解了那么你后面刷任何层相关题目都是在往这个已经建好的骨架上加肉。我自己的刷题路径就是这样先用简单题建立模板再用中等题在模板上做替换练习最后见到新题第一时间就能识别出它属于哪个模板的变体。这种“以模板带题”的方式比单纯按难度刷题要扎实得多。