Zigzag level order traversal

Problem Return the zigzag level-order traversal of a binary tree: level 0 left→right, level 1 right→left, alternating.

Input / Output

• Input: tree root. Output: list of levels, each in its zigzag direction.

Constraints

• Up to 2000 nodes; O(n) required.

Example

• [3,9,20,null,null,15,7] → [[3],[20,9],[15,7]].