Read the Levels in a Zigzag Pattern
Solve this ProblemYou are given the root of a binary tree. Return its levels as lists of values, from the root level downwards, but read the levels in a zigzag: the root level from left to right, the second level from right to left, the third from left to right again, and so on. An empty tree gives an empty list.
A level-order traversal with a queue produces every level from left to right. You can reverse alternate rows afterwards, or track the direction and write each value directly into the position where it belongs.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
0 ≤ number of nodes ≤ 100 - ◆
−100 ≤ node.val ≤ 100 - ◆
The tree is given as its root node (null for an empty tree); each node has a val, a left child and a right child - ◆
Return one list per level, from the root level downwards. The root level is read left to right, the next level right to left, the next left to right again, and so on, alternating. An empty tree gives an empty list
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Collect Rows Normally, Then Reverse Every Other Row
GoodFirst do the ordinary level-by-level traversal with a queue, giving every level in left-to-right order. Afterwards, walk over the list of rows and reverse each odd-numbered row (rows 1, 3, 5, …). It is simple and correct; the drawback is a second pass that touches half of the values again. Time is O(n) for the traversal plus O(n) for the reversals; the rows use O(n) space.
O(n)O(n)1class Solution {
2 public List<List<Integer>> zigzagLevels(TreeNode root) {
3 List<List<Integer>> levels = new ArrayList<>();
4 if (root == null) return levels;
5 Queue<TreeNode> queue = new ArrayDeque<>();
6 queue.add(root);
7 while (!queue.isEmpty()) {
8 int size = queue.size();
9 List<Integer> row = new ArrayList<>();
10 for (int i = 0; i < size; i++) {
11 TreeNode node = queue.poll();
12 row.add(node.val);
13 if (node.left != null) queue.add(node.left);
14 if (node.right != null) queue.add(node.right);
15 }
16 levels.add(row);
17 }
18 for (int d = 1; d < levels.size(); d += 2) {
19 Collections.reverse(levels.get(d));
20 }
21 return levels;
22 }
23}Optimal — Write Each Value Straight Into Its Final Slot
OptimalAlternate a direction flag while doing the level-by-level traversal. On a level of size nodes, the i-th node taken from the queue (in left-to-right order, since the queue is not changed) belongs at position i when the level reads left to right, and at position size − 1 − i when it reads right to left. Create the row with its final size and write every value directly into its slot — no second pass and no reversal. After each level, flip the flag. Every node is handled once: O(n) time; besides the answer itself, the queue holds at most a level or two (O(w)).
O(n)O(w)1class Solution {
2 public List<List<Integer>> zigzagLevels(TreeNode root) {
3 List<List<Integer>> levels = new ArrayList<>();
4 if (root == null) return levels;
5 Queue<TreeNode> queue = new ArrayDeque<>();
6 queue.add(root);
7 boolean leftToRight = true;
8 while (!queue.isEmpty()) {
9 int size = queue.size();
10 int[] slots = new int[size];
11 for (int i = 0; i < size; i++) {
12 TreeNode node = queue.poll();
13 int pos = leftToRight ? i : size - 1 - i;
14 slots[pos] = node.val;
15 if (node.left != null) queue.add(node.left);
16 if (node.right != null) queue.add(node.right);
17 }
18 List<Integer> row = new ArrayList<>();
19 for (int v : slots) row.add(v);
20 levels.add(row);
21 leftToRight = !leftToRight;
22 }
23 return levels;
24 }
25}