Binary Tree Zigzag Level Order Traversal
Medium· BFS
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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)
