Zigzag Level Order

Return the values level by level, but alternate the direction: the first level left to right, the second right to left, the third left to right again, and so on.

The tests write a tree as a level-order list (row by row, left to right) with None for a missing child: [3, 9, 20, None, None, 15, 7] is a root 3 with children 9 and 20, where 20 has children 15 and 7.

For [3, 9, 20, None, None, 15, 7] the answer is [[3], [20, 9], [15, 7]].

Examples

Example 1

Input:

zigzag_level_order(root)  # root = [3, 9, 20, None, None, 15, 7]

Output:

[[3], [20, 9], [15, 7]]

Example 2

Input:

zigzag_level_order(root)  # root = [1, 2, 3, 4, None, None, 5]

Output:

[[1], [3, 2], [4, 5]]

Constraints

• 0 <= number of nodes <= 100000
• -10**9 <= val <= 10**9