Loading…
Loading…
Breadth-first but alternating: the first row goes left to right, the next right to left, spiralling down the tree.
Zigzag traversal walks the tree level by level like BFS, but flips direction on every row.
Output: []
1List<List<Integer>> zigzag(Node root) {2 List<List<Integer>> out = new ArrayList<>();3 Queue<Node> q = new LinkedList<>();4 if (root != null) q.add(root);5 boolean leftToRight = true;6 while (!q.isEmpty()) {7 int size = q.size();8 List<Integer> level = new ArrayList<>();9 for (int i = 0; i < size; i++) {10 Node n = q.poll();11 level.add(n.val);12 if (n.left != null) q.add(n.left);13 if (n.right != null) q.add(n.right);14 }15 if (!leftToRight) Collections.reverse(level);16 out.add(level);17 leftToRight = !leftToRight; // flip the direction each level18 }19 return out;20}