Binary Tree Zigzag Level Order Traversal or Spiral Traversal

Problem Statement:

Given the root of a binary tree, return the zigzag level order traversal of its nodes’ values. (i.e., from left to right, then right to left for the next level and alternate between).

Example 1: Input: root = [3,9,20,null,null,15,7] Output: [[3],[20,9],[15,7]]

Example 2: Input: root = [1] Output: 1

Example 3: Input: root = [] Output: []

Constraints:

• The number of nodes in the tree is in the range [0, 2000].
• -100 <= Node.val <= 100

Solution:

class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        if(root == null){
            return new ArrayList<>();
        }
        Queue<TreeNode> q = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        
        q.add(root);
        boolean leftToRight = true;
 
        while(!q.isEmpty()){
            // Get the number of nodes at the current level
            int size = q.size();
            // Initialize a temporary list to store the current level's values
            List<Integer> temp = new ArrayList<>();
            
            // Process each node at the current level
            for(int i = 0; i < size; i++){
                TreeNode curr = q.poll();
 
                if(leftToRight){
                    temp.add(curr.val);
                } else {
                    temp.add(0, curr.val); // Add to the front of the list to achieve reverse order
                }
                
                if(curr.left != null){
                    q.add(curr.left);
                }
 
                if(curr.right != null){
                    q.add(curr.right);
                }
            }
 
            res.add(temp);
            // Toggle the order for the next level
            leftToRight = !leftToRight;
        }
 
        return res;
    }
}