Binary Tree Zigzag Level Order Traversal

Given the root of a binary tree, return the zigzag level order traversal of its nodes' values. Pattern focus: BFS Level Order with Queue. Alternate the reading direction of each level while preserving breadth-first traversal.

Input Format

root = binary tree root

Output Format

zigzag level order traversal as list of levels

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9
  • root must satisfy the format described in inputFormat.

Examples

Example 1:

Input:

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

Output:

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

Explanation:

The second level is read from right to left.

Example 2:

Input:

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

Output:

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

Explanation:

Traversal direction alternates at each level.

Loading...
Binary Tree Zigzag Level Order Traversal