152. Binary Tree Zigzag Level Order Traversal

Medium · Binary Tree

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. Zigzag means alternate between left-to-right and right-to-left for each level.

For example, level 0 is traversed left-to-right, level 1 is traversed right-to-left, level 2 is traversed left-to-right, and so on.

Examples

Example 1
Input: Tree: [3, 9, 20, null, null, 15, 7]
Output: [[3], [20, 9], [15, 7]]
Explanation: Level 0 (left-to-right): [3]. Level 1 (right-to-left): [20, 9]. Level 2 (left-to-right): [15, 7].
Example 2
Input: Tree: [1, 2, 3, 4, null, null, 5]
Output: [[1], [3, 2], [4, 5]]
Explanation: Level 0 (left-to-right): [1]. Level 1 (right-to-left): [3, 2]. Level 2 (left-to-right): [4, 5].

Constraints