Zigzag Level Order Traversal

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values.

• Level 0: Left -> Right
• Level 1: Right -> Left
• Level 2: Left -> Right
• ...

We use standard BFS with a Queue to process levels one by one.

Handling Zigzag:

1. Collect all values for the current level into a list.
2. Check Depth: If the current level depth is Odd, reverse the list before adding it to results.
3. Alternative: Use a Deque for the current level list, using push_front or push_back depending on depth.

Observe the snake-like pattern of the traversal as nodes are visited.