Zigzag Level-Order

Difficulty: Hard · Topic: Traversals

Return the level-order traversal, but alternate direction each level: the first level left-to-right, the second right-to-left, and so on. The build_tree / TreeNode helper is provided.

Examples

zigzag([3,9,20,null,null,15,7])
→ [[3],[20,9],[15,7]]

Level 1 normal, level 2 reversed.

zigzag([1])
→ [[1]]

Target complexity: time O(n), space O(n)

Write your solution in Python and run it against hidden tests right on this page. Progressive hints and Python + C++ reference solutions are included.

Learn the idea first: the lesson for this problem.