Zigzag Level Order Traversal

mediumSave

Binary TreeBreadth-First SearchTree

Given a binary tree, return the zigzag level order traversal of its nodes' values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1

Input

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

Output

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

Explanation. Level 1: [3], Level 2: [20,9] (Right to Left), Level 3: [15,7] (Left to Right).

Example 2

Input

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

Output

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

Explanation. Level 1: [1], Level 2: [3,2] (Right to Left), Level 3: [4,5] (Left to Right).

Example 3

Input

[
  []
]

Output

[]

Explanation. The tree is empty, so the zigzag level order traversal is also an empty list.

Follow-up: Can you solve the problem without using additional data structures for the level order output?

Constraints:

The number of nodes in the tree is in the range [0, 2000]. Each node's value is between [-10^4, 10^4].

Views: 3