Zigzag Level Order Traversal of Binary Tree

Given a binary tree, perform a zigzag (or spiral) level order traversal.

The zigzag order traversal is defined as follows:

For the first level, traverse from left to right; for the second level, traverse from right to left; and continue alternating for subsequent levels.

The binary tree is given in a comma‐separated string representing its level order traversal. The placeholder null represents an absent child. For instance, the tree

$$3 / \ 9 20 / \ 15 7$$

is represented as 3,9,20,null,null,15,7.

Your task is to output the zigzag level order traversal with each level on a new line. Within each line, the node values should be separated by a space.

inputFormat

The input consists of a single line containing the comma separated values of the tree nodes in level order. Use null to indicate a missing node. For example:

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

outputFormat

Output the zigzag level order traversal of the binary tree. Print each level on a separate line with the node values separated by a single space. If the tree is empty, output nothing.

For example, for the tree represented by 3,9,20,null,null,15,7, the output should be:

3
20 9
15 7

## sample

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

3
20 9
15 7

</p>