Binary Tree Zigzag Level Order Traversal
Return level order traversal, alternating direction each level.
Examples
Input: [3,9,20,null,null,15,7]
Output:
Input: [1]
Output:
Hints
Use a queue to perform a standard level-order traversal (BFS), but track the current level's direction (left-to-right or right-to-left) using a boolean flag.
For each level, determine the number of nodes in advance (using the queue size) and pre-allocate a list of that size to store the nodes in the correct order.
After processing each level, reverse the direction flag and adjust the traversal logic to either append nodes in natural order or reverse order based on the flag.
Binary Tree Zigzag Level Order Traversal
Return level order traversal, alternating direction each level.