Level-Order Tree Zigzag Collector
Problem Description
Given the root of a binary tree, return a list of its node values collected level by level in a **zigzag** pattern: nodes at even-depth levels (0, 2, 4, …) are collected left-to-right, while nodes at odd-depth levels (1, 3, 5, …) are collected right-to-left.
**Example 1:**
```
Input: root = [4, 2, 7, 1, 3, 6, 9]
4
/ \
2 7
/ \ / \
1 3 6 9
Output: [[4], [7, 2], [1, 3, 6, 9]]
```
**Example 2:**
```
Input: root = [1]
Output: [[1]]
```
**Example 3:**
```
Input: root = []
Output: []
```
Constraints
- The number of nodes is in the range [0, 2000]
- -1000 <= Node.val <= 1000
Follow-up
Return the zigzag traversal using only a deque (without any explicit reverse calls) by carefully choosing which end to append children to.
Hints
Try the problem first. If you get stuck, you can reveal hints one at a time.
Solution
Leaderboard
No entries yet for python.
Be the first — submit an accepted solution.