Zigzag Level Order Traversal

Run ordinary BFS and change only how each level is emitted. If root is null, return an empty result. For each level, snapshot the queue size, create a deque, and pop exactly that many nodes. When direction is left-to-right, append each value to the back; when right-to-left, prepend it. Still enqueue left child then right child normally, because traversal order and presentation order are separate concerns. After the level is complete, convert the deque to an array and toggle direction. Each node is visited once, so time is O(n) and space is O(w) for the queue plus the result. Test one node, two levels, a skewed tree, and a level with several values. Avoid reversing the queue itself, which can disturb the next frontier.