Zigzag Level Order Traversal

You are given a binary tree and your task is to perform a zigzag (or spiral) level order traversal. In a zigzag traversal, the nodes of each level are traversed in alternating order: left-to-right for the first level, right-to-left for the second level, and so forth.

Input Format: The first line contains the level order representation of the binary tree. Nodes are given as integers separated by spaces, and a missing (null) child is denoted by the string null.

Output Format: Print the zigzag level order traversal as a sequence of integers separated by spaces.

Example:

Input: 3 9 20 null null 15 7

Output: 3 20 9 15 7

The traversal follows the pattern illustrated by the following formula for level i (0-indexed):

\( T_i = \begin{cases} left\text{-}to\text{-}right, & \text{if } i \mod 2 = 0 \\ right\text{-}to\text{-}left, & \text{if } i \mod 2 = 1 \end{cases} \)

inputFormat

The input is provided via standard input (stdin) and consists of a single line. This line contains the level order traversal of the tree with each node separated by space. Use the string null to represent a missing node.

Example: 1 2 3 4 null null 5

outputFormat

Output the zigzag level order traversal of the tree as a single line to standard output (stdout). The numbers should be separated by a single space.

Example: For the input 1 2 3, the output should be 1 3 2.

## sample

1

1

</p>