Why it works
- When a level starts, the queue holds exactly that level: the level above is all taken out, and none of the level below is in yet.
- size is read before the level puts its children in the queue, so the loop takes exactly the level and the sum is divided by its own count.
- Each node adds its value to the sum of its own level once, so every average is over the right values.
Complexity
Time O(n): each node enters and leaves the queue once. Memory O(w): the queue holds at most about two levels, w is the widest one.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗