103. Binary Tree Zigzag Level Order Traversal
Your function receives the root of a binary tree (possibly empty; each node exposes val, left, and right). Collect the values level by level, but let the reading direction snake back and forth: level 0 is read left to right, level 1 right to left, level 2 left to right again, and so on, alternating all the way down.
Return the levels as a list of lists in that alternating order. An empty tree yields an empty list.
The tree's shape never changes — only the direction in which you read off each row.
Example 1:
Input: root = [3, 9, 20, null, null, 15, 7]
Output: [[3], [20, 9], [15, 7]]
Explanation: Level 0 reads left to right: [3]. Level 1 flips to right-to-left: [20, 9]. Level 2 flips back: [15, 7].
Example 2:
Input: root = [1, 2, 3, 4, 5, 6, 7]
Output: [[1], [3, 2], [4, 5, 6, 7]]
Explanation: The full second row is [2, 3] in tree order; read backwards it becomes [3, 2]. The third row is even-numbered, so it stays [4, 5, 6, 7].
Constraints:
- 0 ≤ number of nodes ≤ 2000
- -1000 ≤ Node.val ≤ 1000
Hints:
Start from a plain level-order traversal (queue + per-level size snapshot). What is the smallest change that flips every other row?
Either reverse each odd-indexed row after collecting it, or avoid the reversal entirely: append to the row's tail on even depths and push onto its head (a deque) on odd depths.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: root = [3, 9, 20, null, null, 15, 7]
Expected output: [[3], [20, 9], [15, 7]]