Binary Tree Zigzag Level Order Traversal
Medium· BFS
Problem
Return the values of a binary tree level by level, but alternate the reading direction: the first level left to right, the second right to left, and so on.
Examples
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Input: root = [1,2,3,4,null,null,5]
Output: [[1],[3,2],[4,5]]
Constraints
- • 0 <= number of nodes <= 2000
- • -100 <= Node.val <= 100
Hints & approach
Hint 1
Start from a normal level-order traversal.
Hint 2
Only the output order of each level changes, not the order you enqueue children.
Approachtry the hints first
Run a standard BFS that collects one list per level. Keep a boolean that flips after every level; when it indicates right-to-left, reverse the level list (or fill it from the back using a deque) before appending it. Traversal order stays unchanged, so the logic stays simple.
Time O(n) · Space O(n)