Zigzag Level Order Traversal of a Binary Tree

Given a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

The binary tree is provided in a level order format as a string. The input format is a single line which is a list of node values enclosed in square brackets. For example: [3,9,20,null,null,15,7], where null indicates that a node does not exist.

Note: The zigzag order traversal means that the first level is traversed from left to right, the next level from right to left, and so on. Formally, if level i contains k elements, then for even-numbered levels, the order is

[ \text{Level}_0: [a_1, a_2, \dots, a_k] \quad\text{,}\quad \text{Level}_1: [a_k, \dots, a_2, a_1] ]

Your task is to implement a function to perform this zigzag level order traversal.

inputFormat

The input is given as a single line from standard input. It is a string representing the level order traversal of a binary tree. The string is formatted as:

[node1,node2,...,nodeN]

Each node is either an integer or the literal null (case-sensitive) to denote an absent node. For example: [3,9,20,null,null,15,7].

outputFormat

Print the zigzag level order traversal of the binary tree as a JSON array of arrays. For example, the output for the tree in the sample above should be:

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

The output should be printed to standard output.

## sample

[ ]

[]