Binary Tree Zigzag Level Order Traversal

Medium~25 min

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values.

The zigzag pattern alternates direction at each level:

Level 0: left to right
Level 1: right to left
Level 2: left to right
... and so on

Return the result as a list of lists, where each inner list contains the node values at that depth level in the appropriate zigzag order.

Each node has a val (integer value), a left child, and a right child. Children may be null.

The tree is given as a level-order array where null represents a missing node. For example, [3,9,20,null,null,15,7] represents:

      3            → Level 0: [3]         (left to right)
     / \
    9  20           ← Level 1: [20, 9]    (right to left)
      /  \
     15   7         → Level 2: [15, 7]    (left to right)

Examples

Example 1

Input: root = [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: root = [1]

Output: [[1]]

Explanation: A single-node tree has one level read left to right.

Example 3

Input: root = []

Output: []

Explanation: An empty tree has no levels.

Constraints

The number of nodes in the tree is in the range [0, 2000]
-100 <= Node.val <= 100
Expected time complexity: O(n)

Code

Ctrl+EnterRun|Ctrl+⇧+EnterSubmit

Output

Run your code to see results

Use Cmd+Enter to run