Problems
Binary Tree Zigzag Level Order Traversal
Medium·Tagstreebfsqueue
Problem Statement
Given the `root` of 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).
Note: Assume a standard `TreeNode` class is already provided in the execution environment, containing `val`, `left`, and `right` properties.
Examples
Example 1
Input
root: [3, 9, 20, null, null, 15, 7]Tree
Output
"[[3], [20, 9], [15, 7]]"Why
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]Tree
Output
"[[1]]"Why
Level 0 (left-to-right): [1]
Example 3
Input
root: []Output
"[]"Why
An empty tree returns an empty array.
Constraints
- •The number of nodes in the tree is in the range [0, 2000].
- •-100 <= Node.val <= 100
Hints
Stuck? Reveal a nudge toward the right pattern, one step at a time.
Hint 1
Start by writing a standard Level Order Traversal using a Queue.
Hint 2
Instead of changing the order in which you enqueue or dequeue nodes, simply maintain a boolean flag called `leftToRight` (initially true).
Hint 3
When you finish collecting the nodes for the current level into a temporary array, check the `leftToRight` flag. If it's false, reverse the temporary array before appending it to your final result!
Hint 4
Don't forget to toggle the `leftToRight` flag at the end of every level.