ZigZag Tree Traversal

You get the root of a binary tree. Return an array with one list per level, from the top down.

Each list holds the values of one level. The direction switches on every level. Read the first level from left to right. Read the next one from right to left. Then keep switching.

Trees are written level by level, from top to bottom and left to right. A nil marks a missing child.

Example 1:

Input: root = [1, 2, 3, 4, 5, nil, 6, nil, nil, 7, 8]
      1
     / \
    2   3
   / \   \
  4   5   6
     / \
    7   8

Output:
[
  [1],
  [3,2],
  [4,5,6],
  [8,7]
]
Explanation: Levels 1 and 3 are read left to right.
Levels 2 and 4 are read right to left.

Example 2:

Input: root = [6]
Output:
[
  [6]
]

Constraints:

• 1 to 1,000 nodes.
• Each value is a whole number from 1 to 1,000.
• No two nodes have the same value.