Read a binary tree one level at a time, from the root downwards, but switch direction on every level. The root's level is read left to right, the level below it right to left, the next one left to right again, and so on.
Given the root of a binary tree, return one list per level, holding that level's values in the order they are read. An empty tree gives an empty list.
The second level is read right to left, 8 before 3. The third goes back to left to right: 1, 4, 9. The gap under 8 doesn't change the order of the nodes that are there.
The direction belongs to the level, not to the side a node hangs on: -2 is a right child, yet its children are still read left to right, because they are on the third level.
Constraints
0 and 2000 nodes.-100 <= Node.val <= 100This is an ordinary level-by-level walk. Only the order in which each level is written out changes.