Binary Tree Zigzag Level Order Traversal

Pseudo-Palindromic Paths in a Binary Tree

Lowest Common Ancestor of a Binary Tree

Return binary-tree values level by level, alternating left-to-right and right-to-left order.

Given the `root` of a binary tree, return the zigzag level order traversal of its nodes' values — left to right for level 0, right to left for level 1, then alternating for each subsequent level.

**Input / output**
- Input: `root: TreeNode` (JSON test fixture uses a LeetCode-style level-order array such as `[3,9,20,null,null,15,7]`, with `null` for missing children)
- Output: `int[][]`

## Example 1
```json
Input: {"root":[3,9,20,null,null,15,7]}
Output: [[3],[20,9],[15,7]]
```

## Example 2
```json
Input: {"root":[1]}
Output: [[1]]
```

## Example 3
```json
Input: {"root":[]}
Output: []
```

## Constraints
- 0 <= number of nodes <= 2000
- -100 <= Node.val <= 100

## Follow-up
Can you do this in one BFS pass without calling `reverse()` on every other level, by placing each value directly into its final index for that level?

The key pattern is: BFS processes one queue level at a time while a direction flag decides where each value lands. Identify the state and invariant before coding.

Recognize the Pattern

Advance one state transition at a time. Mark or update state before exploring dependent work.

Build the Algorithm

Test empty or minimal input, skewed shapes, duplicates where allowed, and impossible outcomes.

Check Edge Cases

Time: O(n) — every node is visited once. Space: O(w) for the queue and current level buffer, where w is the widest level of the tree (O(n) worst case).

All 7 languages below implement the same level-order BFS, flipping the write direction after each level.