#103
Binary Tree Zigzag Level Order Traversal
Medium BFS with alternating direction
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
Return level-order values, but alternate direction each level: left-to-right, then right-to-left, and so on.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: level order, but alternating left-to-right and right-to-left.
Why this works: normal BFS; on odd levels add values to the front of the level list.
Example: 3 (9, 20 (15, 7))
[3], [20, 9], [15, 7]✦Hints open one at a time
Do normal BFS.
For odd levels, add values at the front of the level list.
↗Approach
Level-order BFS with a flag. Use a LinkedList per level and addLast or addFirst depending on the flag.
</>Solution (Java)
import java.util.*;
/**
* class TreeNode { int val; TreeNode left, right; } // provided by LeetCode
*/
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> res = new ArrayList<>();
if (root == null) return res;
Queue<TreeNode> q = new ArrayDeque<>();
q.offer(root);
boolean leftToRight = true;
while (!q.isEmpty()) {
LinkedList<Integer> level = new LinkedList<>();
for (int i = q.size(); i > 0; i--) {
TreeNode n = q.poll();
if (leftToRight) level.addLast(n.val);
else level.addFirst(n.val); // reverse only the output
if (n.left != null) q.offer(n.left);
if (n.right != null) q.offer(n.right);
}
res.add(level);
leftToRight = !leftToRight;
}
return res;
}
}!Common mistake
Changing the order you push children into the queue — that scrambles the next levels.
Complexity
- Time: O(n).
- Space: O(w).
Topic: Binary Trees
🎬 Episodes 53–60: video coming soon