Zigzag level order traversal
viaLeetCode
Problem Return the zigzag level-order traversal of a binary tree: level 0 left→right, level 1 right→left, alternating.
Input / Output
- Input: tree root. Output: list of levels, each in its zigzag direction.
Constraints
- Up to 2000 nodes; O(n) required.
Example
- [3,9,20,null,null,15,7] → [[3],[20,9],[15,7]].
Expected approach
- Standard BFS by level; for right-to-left levels either fill the level list backwards (LinkedList addFirst / preallocated array by index) or reverse after collection — insertion-time reversal avoids the extra pass. A flag flips per level. O(n)/O(width). The two-stack alternative (current/next stack with push-order flipping) is the classic non-BFS answer worth naming. Probes: preserving nulls' absence, very wide trees (queue memory).
asked …