Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. In other words, the first level is traversed from left to right, the second from right to left, and so on.

For a binary tree with levels denoted by \(L_0, L_1, L_2, \dots\), the output should be a list of lists \( [L_0, L_1, L_2, \dots] \) where each \(L_i\) is the sequence of node values at that level in the required order.

The tree is provided in level order format. A special token null denotes a missing node.

inputFormat

The input begins with an integer n representing the number of tokens in the level order traversal of the binary tree. If n = 0, the tree is empty. Otherwise, the next n tokens are space-separated values representing the nodes of the tree in level order. Use the token null (without quotes) to denote a missing node. All non-null tokens represent integers.

Example:

7
1 2 3 4 5 6 7

outputFormat

Output the zigzag level order traversal of the binary tree as a list of lists. The output should exactly match the format shown in the examples.

Example:

[[1],[3,2],[4,5,6,7]]

## sample

0

[]