Why it works
- The queue is never turned around: children always go in left first, so each level comes out of it left to right, as in plain level order.
- On a right-to-left level each value is put in front of the ones before it, so the level is written reversed at no extra cost.
- leftToRight flips after every level, so the directions alternate starting with left to right.
Complexity
Time O(n): each node enters and leaves the queue once, and addFront takes one step on a double-ended list. Memory O(n): the answer holds every value, the queue at most about two levels.
nextNow solve it yourself, no hints.
Solve on LeetCode ↗