Zigzag Level Order Traversal of a Binary Tree

Given a binary tree, perform a zigzag level order traversal of its nodes' values. In a zigzag traversal, the nodes on the first level are traversed from left to right, the nodes on the second level are traversed from right to left, the third level again from left to right, and so on.

More formally, let \(L_i\) denote the list of nodes at the \(i\text{-th}\) level (with the root considered as level 1). Then for each level \(i\):

• If \(i\) is odd, traverse \(L_i\) from left to right.
• If \(i\) is even, traverse \(L_i\) from right to left.

Your task is to read a binary tree from the input (in level order with null representing a missing node) and print its zigzag level order traversal as a list of lists.

inputFormat

The input consists of a single line containing space-separated tokens representing the binary tree in level order. Each token is either an integer or the string null (without quotes) to denote a missing node. Note that the input may represent an empty tree.

For example, the input:

1 2 3 4 5 6 7

represents the following tree:

        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.

For the above example, the output should be:

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

## sample

1 2 3 4 5 6 7

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