Given the root of a binary tree, return the zigzag level order traversal of its nodes' values (left to right, then right to left for the next level, alternating).
Example 1
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]
Explanation: Level 0 left-to-right: [3]. Level 1 right-to-left: [20,9]. Level 2 left-to-right: [15,7].
The number of nodes is in the range [0, 2000]Start from plain BFS level-order traversal — process one level (queue snapshot) at a time.
The only new piece is direction: track whether the current level should be reversed before adding it to the result.
Don't reverse how you traverse the queue — collect the level normally, then reverse the resulting list only on alternate levels. Simpler and less error-prone than trying to alternate the traversal direction itself.
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(); // snapshot — exactly this many nodes belong to the current level
List<Integer> level = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) queue.offer(node.left);
if (node.right != null) queue.offer(node.right);
}
if (!leftToRight) Collections.reverse(level);
result.add(level);
leftToRight = !leftToRight;
}
return result;
}Time: O(n) · Space: O(n)