Given the root of a binary tree, return the zigzag level order traversal of its nodes' values (i.e., from left to right, then right to left for the next level, alternating).

Example 1:

Input:  3 9 20 null null 15 7
Output:
3
20 9
15 7

Example 2:

Input:  1
Output:
1

Constraints:

• The number of nodes is in the range [0, 2000]
• -100 ≤ Node.val ≤ 100

Input format: BFS level-order, space-separated, null for missing nodes.

Output format: One line per level, space-separated. Even levels left-to-right; odd levels right-to-left.