Given the root of a binary tree, return the average value of the nodes
on each level in the form of an array. Answers within 10-5 of the actual answer are accepted.
Input: root = [3,9,20,null,null,15,7]
Output: [3.0, 14.5, 11.0]
Explanation: Level 0 avg = 3/1 = 3.0. Level 1 avg = (9+20)/2 = 14.5. Level 2 avg = (15+7)/2 = 11.0.
Input: root = [3,9,20,15,7]
Output: [3.0, 14.5, 11.0]
Constraints:
- 1 <= Number of nodes <= 104
- -231 <= Node.val <= 231 - 1
Contents
- Solution — BFS Level Order
- Complexity Analysis
BFS Level Order
Perform level-order BFS. For each level, accumulate the sum and count the nodes. Divide the sum
by the count to get the average. Use a double (or long) accumulator
to avoid integer overflow — node values can be up to 231-1 and a level can have many nodes.
Algorithm:
- Enqueue root.
- While queue is non-empty, capture levelSize = queue.size().
- Dequeue levelSize nodes, accumulating their values as double.
- Compute average as sum / levelSize and add to result.
public List<Double> averageOfLevels(TreeNode root) {
List<Double> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
double sum = 0;
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
sum += node.val;
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(sum / levelSize);
}
return result;
}
Using double sum prevents integer overflow since node values can be close to Integer.MAX_VALUE and a level can have thousands of nodes.
- Time: O(n) — every node is enqueued and dequeued exactly once.
- Space: O(n) — the queue holds at most n/2 nodes at the widest level of the tree.