Zig-Zag Level Order Traversal of Binary Tree

Given a binary tree, your task is to perform a zigzag level order traversal. This traversal starts from left to right on the first level, then switches to right to left on the next level, and continues to alternate in this manner.

Input:

The first line contains an integer 'T', representing the number of test cases. Each test case consists of a single line containing the elements in level order, where nodes are separated by a space. Use -1 to represent null nodes, which are not part of the tree.

Output:

For each test case, output a single line with zigzag level order traversal of the tree's nodes, separated by spaces.

Example:

Input:

1
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 tree has the following levels:

• Level 1: nodes {1}
• Level 2: nodes {3, 2}
• Level 3: nodes {4, 5, 6}
• Level 4: nodes {7}

The zigzag traversal adheres to the pattern of navigating from left to right, then right to left for alternating levels.

Constraints:

• 1 ≤ T ≤ 100
• 0 ≤ N ≤ 3000
• 0 ≤ val ≤ 105

Note: The input ends when all nodes at the last level are null (-1). You do not need to handle printing within your function.