Zigzag Level Order Traversal of a Binary Tree

Given a binary tree, your task is to output its zigzag level order traversal. In a zigzag order, nodes at the first level are traversed from left to right, nodes at the second level from right to left, and so on. Formally, for level \(i\):

[ \text{order}_{i}=\begin{cases} \text{left-to-right} & \text{if } i \text{ is even},\ \text{right-to-left} & \text{if } i \text{ is odd}. \end{cases} ]

The binary tree is provided in level order as space separated tokens. A token contains either an integer or the string null which indicates the absence of a node. For example, the input 3 9 20 null null 15 7 represents the tree:

    3
   / \
  9   20
     /  \
    15   7

Your output should be a list of lists, where each inner list contains the values at that level in the required zigzag order.

inputFormat

The input is a single line read from standard input consisting of space separated tokens. Each token is either an integer or the string null. The first token represents the root of the tree. For example:

3 9 20 null null 15 7

outputFormat

Output the zigzag level order traversal of the binary tree as a list of lists. The output should be printed to standard output. For example:

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

## sample

3 9 20 null null 15 7

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