83.二叉树的层平均值
题目
给定一个非空二叉树的根节点 root , 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5 以内的答案可以被接受。
示例 1：
- 输入：root = [3,9,20,null,null,15,7]
- 输出：[3.00000,14.50000,11.00000]
- 解释：第 0 层的平均值为 3,第 1 层的平均值为 14.5,第 2 层的平均值为 11 。
- 因此返回 [3, 14.5, 11] 。
示例 2:
- 输入：root = [3,9,20,15,7]
- 输出：[3.00000,14.50000,11.00000]
提示：
- 树中节点数量在 [1, 104] 范围内
- -231 <= Node.val <= 231 - 1
思路
还是BFS层序遍历，每层做三件事:
- 进层前先记下 levelSize（这一层有几个节点）
- 循环把这一层全部出队，累加节点值到 sum
- sum / levelSize 就是这层平均值，同时把子节点塞进队尾准备下一层
本题的陷阱: 求和会溢出
本题唯一的真陷阱：求和会溢出
看题目的数据范围：
▎ 节点数最多 10^4，节点值范围 -2^31 <= Node.val <= 2^31 - 1
2^31 - 1 就是 Int.MAX_VALUE。也就是说，单个节点的值就可能顶到 Int 的天花板。
那如果某一层有两个节点，都是 Int.MAX_VALUE 呢？
var sum = 0 // Int 类型
sum += Int.MAX_VALUE // 2147483647
sum += Int.MAX_VALUE // 溢出！变成 -2
// 平均值算出来 = -1.0，实际应该是 2147483647.0
解决方法就是: sum用Long
class TreeNode(var `val`: Int) {
var left: TreeNode? = null
var right: TreeNode? = null
}
class Solution {
/**
* 求二叉树每一层的平均值
*
* 核心思想：标准 BFS 层序遍历模板。
* 进入每一层前先固定这一层的节点数，把整层出队累加求和，再除以个数。
*
* 时间复杂度 O(n)：每个节点进出队列各一次
* 空间复杂度 O(w)：w 为树的最大宽度，最坏约 n/2（满二叉树的最后一层）
*/
fun averageOfLevels(root: TreeNode?): DoubleArray {
val res = mutableListOf<Double>()
if (root == null) {
return DoubleArray(0)
}
// ArrayDeque 当队列：尾部入队，头部出队
val queue = ArrayDeque<TreeNode>()
queue.addLast(root)
while (queue.isNotEmpty()) {
// ⚠️ 关键 1：先把本层节点数固定住。
// 循环体里会往队尾塞下一层节点，queue.size 会一直变大。
val levelSize = queue.size
// ⚠️ 关键 2：必须用 Long！
// 节点值最大可达 Int.MAX_VALUE，两个就能把 Int 撑爆。
var sum = 0L
repeat(levelSize) {
val node = queue.removeFirst()
sum += node.`val` // Int 自动提升为 Long，不会溢出
// 把下一层的节点接上（顺序无所谓，反正要全部求和）
node.left?.let { queue.addLast(it) }
node.right?.let { queue.addLast(it) }
}
// 用 toDouble() 做浮点除法。
// 若写成 sum / levelSize 会变成整数除法，14.5 会被截成 14
res.add(sum.toDouble() / levelSize)
}
return res.toDoubleArray()
}
}
复杂度
- 时间复杂度: O(n)
- 空间复杂度: O(w) 最大宽度
- 邮箱 ：charon.chui@gmail.com
- Good Luck!