Binary Tree Zigzag Level Order Traversal
The key idea
Do a normal breadth-first level-order traversal, but flip the direction every level. Collect each level left to right as usual, then reverse the even-indexed levels (or reverse on alternate levels) so the output zigzags.
Problem
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).
Constraints
- The number of nodes in the tree is in the range
[0, 2000]. -100 <= Node.val <= 100
Examples
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Input: root = [1]
Output: [[1]]
Input: root = []
Output: []
Complexity
Time: O(n) Space: O(n)
See the full solution
- ✓Full worked approach
- ✓Reference code in 5 languages
- ✓Problem-solving tips
- ✓Step-by-step animated visualization
More BFS / DFS problems
- 01 MatrixMEDIUM
- Average of Levels in Binary TreeEASY
- Binary Tree Level Order TraversalMEDIUM
- Binary Tree Level Order Traversal IIMEDIUM
- Binary Tree Right Side ViewMEDIUM
- Find Bottom Left Tree ValueMEDIUM
- Find Largest Value in Each Tree RowMEDIUM
- Flood FillEASY
- Keys and RoomsMEDIUM
- Max Area of IslandMEDIUM
- Maximum Level Sum of a Binary TreeMEDIUM
- Minimum Depth of Binary TreeEASY