Zigzag Level Order Traversal of a Binary Tree

You are given a binary tree. Your task is to perform a zigzag level order traversal of its nodes' values. In a zigzag traversal, nodes at the first level are traversed from left to right, nodes at the second level from right to left, and the order of traversal alternates with each level.

The binary tree is provided as a level order serialized string where each node value is separated by space, and missing nodes are denoted by the keyword null. Your program should construct the binary tree from this input and then output the zigzag traversal as a sequence of integers separated by spaces.

Note: If the tree is empty, print an empty line.

Mathematically, if we denote by \(L_i\) the list of values at level \(i\), then the output is given by \[ \text{result} = L_0 \oplus L_1^R \oplus L_2 \oplus L_3^R \oplus \cdots, \] where \(L^R\) indicates the list reversed.

inputFormat

The input is provided as a single line from standard input. The line contains the level order serialization of the binary tree. Each token in the line represents a node's value (an integer) or the keyword null for an absent child. Nodes are separated by a single space.

Examples:

• 1 2 3 4 5 6 7
• 1 2 null 3 (represents a tree with root 1, left child 2, and 2's left child 3)
• null (represents an empty tree)

outputFormat

Output the zigzag level order traversal to standard output as a single line. The node values should be separated by a single space. If the tree is empty, output an empty line.

1 2 3 4 5 6 7

1 3 2 4 5 6 7