Zigzag Level Order Traversal

You are given a binary tree. Your task is to perform a zigzag level order traversal on the tree. In other words, for the first level, traverse from left to right; for the second level, traverse from right to left; for the third, from left to right again; and so on.

The binary tree is provided in level order where the value null indicates that there is no node present in that position.

For example, given the following tree:

3, 9, 20, null, null, 15, 7

The zigzag level order traversal returns:

[ [3], [20, 9], [15, 7] ]

Note: If the tree is empty, output nothing.

The process can be mathematically illustrated as follows: Let \(L_i\) denote the list of node values at level \(i\). Then the output is given by:

[ output = \begin{cases} L_1, & \text{if } i=1\ \text{reverse}(L_2), & \text{if } i=2\ L_3, & \text{if } i=3\ \vdots & \vdots \end{cases} ]

inputFormat

The input is provided from standard input (stdin) as a single line containing the node values of the binary tree in level order, separated by spaces. The value null denotes an empty node.

For example:

3 9 20 null null 15 7

outputFormat

Output the zigzag level order traversal result to standard output (stdout). Each level's values should be printed on a separate line with the numbers separated by a single space.

For the above example, the output should be:

3
20 9
15 7

## sample

3 9 20 null null 15 7

3
20 9
15 7

</p>