Binary Tree Zigzag Level Order Traversal

1public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
2    if (root == null) {
3        return new ArrayList<>();
4    }
5
6    List<List<Integer>> result = new ArrayList<>();
7    Queue<TreeNode> queue = new LinkedList<>();
8    queue.offer(root);
9    int level = 0;
10
11    while (!queue.isEmpty()) {
12        int levelSize = queue.size();
13        List<Integer> currentLevel = new ArrayList<>();
14
15        for (int i = 0; i < levelSize; i++) {
16            TreeNode node = queue.poll();
17            currentLevel.add(node.val);
18
19            if (node.left != null) {
20                queue.offer(node.left);
21            }
22            if (node.right != null) {
23                queue.offer(node.right);
24            }
25        }
26
27        // Reverse if odd level (right-to-left)
28        if (level % 2 == 1) {
29            Collections.reverse(currentLevel);
30        }
31
32        result.add(currentLevel);
33        level++;
34    }
35
36    return result;
37}