Given the root of a binary tree, return the zigzag level order traversal
of its node values. Even-depth levels are traversed left to right; odd-depth levels are traversed
right to left.
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Explanation: Level 0 (L→R): [3]. Level 1 (R→L): [20,9]. Level 2 (L→R): [15,7].
Input: root = [1]
Output: [[1]]
Constraints:
- 0 <= Number of nodes <= 2000
- -100 <= Node.val <= 100
Contents
- Solution — BFS with Direction Flag
- Complexity Analysis
BFS with Direction Flag
Standard BFS with a boolean leftToRight flag. For each level, collect the node
values in a LinkedList. When the flag is true, append values to the tail
(left-to-right order); when false, prepend values to the head (right-to-left order). Toggle the
flag after each level. Children are always enqueued left-before-right.
Algorithm:
- Enqueue root; initialize leftToRight = true.
- For each level, create a LinkedList<Integer>.
- If leftToRight, add to the end (addLast); else add to the front (addFirst).
- After the level, toggle leftToRight and add the list to results.
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) return result;
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
boolean leftToRight = true;
while (!queue.isEmpty()) {
int levelSize = queue.size();
LinkedList<Integer> level = new LinkedList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
if (leftToRight) {
level.addLast(node.val);
} else {
level.addFirst(node.val); // prepend for R→L
}
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
result.add(level);
leftToRight = !leftToRight; // toggle direction
}
return result;
}
Trace through Example 1: root = [3,9,20,null,null,15,7]
| Level | Direction | Nodes | Level output |
|---|
| 0 | L→R | 3 | [3] |
| 1 | R→L | 9, 20 | [20, 9] |
| 2 | L→R | 15, 7 | [15, 7] |
- Time: O(n) — each node is processed exactly once; LinkedList head/tail operations are O(1).
- Space: O(n) — queue holds at most n/2 nodes at the widest level.