Why it works
- The queue gives nodes out in the order they came in, so a whole level leaves it before any node of the level below.
- When a level starts, the queue holds exactly that level. size is read then, so the loop stops at the level’s end, even though children of the next level are already queued behind it.
- Children go in left first, so each level comes out left to right, whichever parent a node hangs from.
Complexity
Time O(n): each node enters and leaves the queue once. Memory O(n): the answer holds every value, and the queue up to about two levels.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗