二叉树的层平均值

记住「队列按层展开,每层求和再除以个数」,下面逐帧套它。

什么是层：先找感觉:同一深度的节点属于同一层。根 48 是第 0 层,孩子 31、70 是第 1 层,再往下 24、36、60、20 是第 2 层。我们要在每一层里把所有值加起来、除以个数得平均。

第 0 层就位：进入第 0 层,队列里是 [48]。先把这一整层从左到右扫一遍,边扫边把值累进「本层和」、并数清「个数」。

第 0 层 · 累加：从队首取出 48(红),把它累加进本层和:0 + 48 = 48,个数变成 1。这是本层最后一个。

第 0 层 · 收孩子：48 加完了。把它的非空孩子 31、70(蓝色)加入下一层,目前下一层攒到了 [31、70]。

第 0 层平均 = 48：第 0 层整层扫完:和是 48、共 1 个,平均 48 ÷ 1 = 48,记进答案。现在各层平均是 [48]。下一层 [31、70] 已就绪,继续。

第 1 层就位：进入第 1 层,队列里是 [31、70]。先把这一整层从左到右扫一遍,边扫边把值累进「本层和」、并数清「个数」。

第 1 层 · 累加：从队首取出 31(红),把它累加进本层和:0 + 31 = 31,个数变成 1。本层还剩 [70] 没加。

第 1 层 · 收孩子：31 加完了。把它的非空孩子 24、36(蓝色)加入下一层,目前下一层攒到了 [24、36]。

第 1 层 · 累加：从队首取出 70(红),把它累加进本层和:31 + 70 = 101,个数变成 2。这是本层最后一个。

第 1 层 · 收孩子：70 加完了。把它的非空孩子 60、20(蓝色)加入下一层,目前下一层攒到了 [24、36、60、20]。

第 1 层平均 = 50.5：第 1 层整层扫完:和是 101、共 2 个,平均 101 ÷ 2 = 50.5,记进答案。现在各层平均是 [48、50.5]。下一层 [24、36、60、20] 已就绪,继续。

第 2 层就位：进入第 2 层,队列里是 [24、36、60、20]。先把这一整层从左到右扫一遍,边扫边把值累进「本层和」、并数清「个数」。

第 2 层 · 累加：从队首取出 24(红),把它累加进本层和:0 + 24 = 24,个数变成 1。本层还剩 [36、60、20] 没加。

第 2 层 · 收孩子：24 是叶子,没有孩子可加,下一层暂时还是 [空]。

第 2 层 · 累加：从队首取出 36(红),把它累加进本层和:24 + 36 = 60,个数变成 2。本层还剩 [60、20] 没加。

第 2 层 · 收孩子：36 是叶子,没有孩子可加,下一层暂时还是 [空]。

第 2 层 · 累加：从队首取出 60(红),把它累加进本层和:60 + 60 = 120,个数变成 3。本层还剩 [20] 没加。

第 2 层 · 收孩子：60 是叶子,没有孩子可加,下一层暂时还是 [空]。

第 2 层 · 累加：从队首取出 20(红),把它累加进本层和:120 + 20 = 140,个数变成 4。这是本层最后一个。

第 2 层 · 收孩子：20 是叶子,没有孩子可加,下一层暂时还是 [空]。

第 2 层平均 = 35：第 2 层整层扫完:和是 140、共 4 个,平均 140 ÷ 4 = 35,记进答案。现在各层平均是 [48、50.5、35]。没有下一层了,BFS 结束。

完成：每一层的平均值依次是 [48、50.5、35]。回头看,就是一遍标准的按层 BFS,每层从左到右把值加起来、再除以个数,一次遍历就出全部答案,时间 O(n)。

边界:空树返回空、单节点即自身、负数照常累加求平均。

两个追问:DFS 带 depth 也能做;按层 BFS 框架解一大类题。