# Binary Tree Zigzag Level Order Traversal

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 and alternate between).

**Example 1:**

**Input:** root = [3,9,20,null,null,15,7]

**Output:** [[3],[20,9],[15,7]]

**Complexity Analysis**

- Time Complexity: O(
*N*), where*N*is the number of nodes in the tree. - Space Complexity: O(
*H*), where*H*is the height of the tree,*i.e.*the number of levels in the tree, which would be roughly log2*N*.