Zigzag Level Order Traversal

You are given a binary tree. Your task is to perform a zigzag level order traversal (also known as spiral order traversal) on the tree and output the result.

The traversal should alternate between left-to-right and right-to-left order at each level. For example, if the first level is traversed from left to right, then the second level should be traversed from right to left, the third again from left to right, and so on.

The binary tree is provided in level order as input, where missing children are denoted by the token #. You are required to build the tree from the input and then perform the zigzag traversal.

The answer must be produced in the exact format as shown in the examples below. If a mathematical formula appears in your explanation, please ensure it is in LaTeX format.

inputFormat

The input is given in one line using standard input. The line contains space-separated tokens representing the nodes in level order. Each token is either an integer or the character # indicating a missing node.

For example: 3 9 20 # # 15 7

outputFormat

Output the zigzag level order traversal as a list of lists in the exact format. That is, print the entire result on one line to standard output with the same structure as Python’s list-of-lists representation.

For example: [[3], [20, 9], [15, 7]]

3 9 20 # # 15 7

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