1. 题目
给定一个非空二叉树的根节点 root
, 以数组的形式返回每一层节点的平均值。与实际答案相差 10-5
以内的答案可以被接受。
示例 1:
1 2 3 4
| 输入: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:
1 2
| 输入:root = [3,9,20,15,7] 输出:[3.00000,14.50000,11.00000]
|
提示:
- 树中节点数量在
[1, 104]
范围内
-2^31 <= Node.val <= 2^31 - 1
2. 思路
- 已知题目要求计算出二叉树每层的平均值,初始化结果列表
result
与层序遍历所需要用到的存储队列queue
- 采用层序遍历的形式,在遍历完每一层的节点后,将该值进行平均计算,并在每一层计算完成后将结果记录入
result
- 完成遍历后可直接返回
result
作为结果列表
3. 代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48
|
class Solution { public List<Double> averageOfLevels(TreeNode root) { if (root == null) { return List.of(); }
var result = new ArrayList<Double>(); var queue = new ArrayDeque<TreeNode>(); queue.offer(root); while (!queue.isEmpty()) { var size = queue.size(); var totalSum = 0.0;
for (var i = 0; i < size; ++i) { var node = queue.poll(); totalSum += node.val;
if (node.left != null) { queue.offer(node.left); }
if (node.right != null) { queue.offer(node.right); } }
result.add(totalSum / size); }
return result; } }
|
4. 复杂度
Author:
zchengb
License:
Copyright (c) 2019-2024 zchengb