Zigzag Level Order Traversal of a Binary Tree

Given the root of a binary tree, perform a zigzag level order traversal of its nodes' values. In other words, traverse the tree level by level, but alternate between left-to-right and right-to-left order for each level.

The zigzag order can be mathematically defined as follows: if the levels of the tree are numbered starting with 0 at the root, then for every even indexed level (0, 2, 4, ...) traverse nodes from left to right, and for every odd indexed level (1, 3, 5, ...) traverse nodes from right to left. In other words, for level \(i\), if \(i \mod 2 = 0\) traverse in normal order, otherwise traverse in reverse order.

You are required to read the input from stdin and output the result to stdout.

inputFormat

The input is given as a single line of space-separated tokens representing the level order serialization of the binary tree. Each token is either an integer (representing a node's value) or the string null to denote a missing node. For example:

3 9 20 null null 15 7

This represents the binary tree:

[ 3 /
9 20 /
15 7 ]

Note that the input is guaranteed to be valid and non-empty for non-empty trees. For an empty tree, the input will be a single token null.

outputFormat

The output should be a single line containing the zigzag level order traversal of the binary tree. The result is represented as a list of lists. For example:

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

Make sure to output the result exactly in this format.

## sample

3 9 20 null null 15 7

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