Zigzag Binary Tree Traversal Problem Statement

Determine the zigzag level order traversal of a given binary tree's nodes. Zigzag traversal alternates the direction at each level, starting from left to right, then right to left, and so on.

Example:

Input:

Binary tree represented as level order traversal: 1 2 3 4 -1 5 6 -1 7 -1 -1 -1 -1 -1 -1

Output:

{{1}, {3, 2}, {4, 5, 6}, {7}}

Explanation:

The provided input represents the binary tree:

The zigzag traversal of this tree is: Level 1 (left to right): 1, Level 2 (right to left): 3, 2, Level 3 (left to right): 4, 5, 6, Level 4 (right to left): 7.

Constraints:

• 1 <= T <= 100
• 0 <= N <= 3000
• 0 <= val <= 10⁵

Note:

Your implementation should return the correct traversal for each test case without formatting the output.