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

For example:
Given binary tree [3,9,20,null,null,15,7],
    3
   /   9  20
    /     15   7
return its zigzag level order traversal as:
[
  [3],
  [20,9],
  [15,7]
]

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> ans = new ArrayList<>();
        
        if (root == null) {
            //ans.add(list);
            return ans;
        }
        Queue<TreeNode> q = new LinkedList<>();
        int deep = 0;
        q.offer(root);
        while (!q.isEmpty()) {
            int size = q.size();
            deep++;
            List<Integer> list = new ArrayList<>();
            
             for (int i = 0; i < size; i++) {
                TreeNode cur = q.poll();
                list.add(cur.val);

               
                if (cur.left != null) {
                    q.offer(cur.left);
                }
                  if (cur.right != null) {
                    q.offer(cur.right);
                }
            }
            if (deep  % 2 == 1) {
                ans.add(list);
            } else {
                reverse(list);
                ans.add(list);
            }
                        
        }
        return ans;
    }
    private void reverse(List<Integer> list) {
        int i = 0, j = list.size() - 1;
        while (i < j) {
            int temp = (int)list.get(i);
            list.set(i, list.get(j));
            list.set(j, temp);
            i++; 
            j--;
        }
    }
}

public class Solution {
    public List<List<Integer>> zigzagLevelOrder(TreeNode root) 
    {
        List<List<Integer>> sol = new ArrayList<>();
        travel(root, sol, 0);
        return sol;
    }
    
    private void travel(TreeNode curr, List<List<Integer>> sol, int level)
    {
        if(curr == null) return;
        
        if(sol.size() <= level)
        {
            List<Integer> newLevel = new LinkedList<>();
            sol.add(newLevel);
        }
        
        List<Integer> collection  = sol.get(level);
        if(level % 2 == 0) collection.add(curr.val);
        else collection.add(0, curr.val);
        
        travel(curr.left, sol, level + 1);
        travel(curr.right, sol, level + 1);
    }
}