Why it works
- The queue holds the nodes in level order: the children go to the back, behind every node of the level still waiting.
- So while i < size, the front of the queue is the next node on the same level, whichever parent it hangs from.
- The last node of a level (i = size) sees the next level at the front, so its next is left as none.
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 level.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗