Zigzag Level Order Traversal

Given a binary tree, return the zigzag (or spiral) level order traversal of its nodes' values. In this traversal, the nodes at each level are visited from left to right, then right to left in the next level, alternating as the levels progress.

The tree is provided as a level order sequence in which the string null indicates that a node is missing.

The zigzag order for the tree below, for example:

    3
   / \
  9  20
    /  \
   15   7

is: [[3], [20, 9], [15, 7]].

inputFormat

The input is a single line containing space-separated tokens representing the binary tree in level order. Each token is either an integer (node value) or the string null for missing nodes.

outputFormat

Output the zigzag level order traversal of the binary tree. The result should be printed to standard output as an array of arrays (list of lists), where each inner array represents a level in the tree.

3 9 20 null null 15 7

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