All problems

Binary Tree Zigzag Level Order Traversal

Medium · tree bfs

You are given the root of a binary tree. Read its values one level at a time, but swap the reading direction on every level, like a snake crossing a board.

• The root's level (the top one) is read from left to right.
• The next level down is read from right to left.
• The one after that is left to right again, and so on, alternating all the way down.

Return a list of lists, one list per level, from the top level to the bottom one. "Left" and "right" mean the positions of the nodes in the picture of the tree, whatever their parents are. An empty tree returns an empty list [].

Examples

Example 1

Input: root = [5, 1, 8, null, 2, 6, 9]

Output: [[5], [8, 1], [2, 6, 9]]

The middle level is 1 then 8 from left to right, so it is reported as 8, 1. The bottom level goes back to left to right.

Example 2

Input: root = [1, 2, 3, 4, 5, 6, 7]

Output: [[1], [3, 2], [4, 5, 6, 7]]

Example 3

Input: root = []

Output: []

There are no levels at all, so there are no lists.

Constraints

• The number of nodes is in the range [0, 500].
• -1000 <= Node.val <= 1000