Binary Tree Zigzag Level Order Traversal

    public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        // write your code here
           ArrayList result  = new ArrayList();
        if(root == null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();

        queue.offer(root);
        boolean normal = true;


        while(! queue.isEmpty()){
            int size = queue.size();
            ArrayList<Integer> list = new ArrayList<Integer>();
            for(int i = 0 ; i < size; i++){
                TreeNode cur = queue.poll();
                if(cur.left != null){
                    queue.offer(cur.left);
                }
                if(cur.right != null){
                    queue.offer(cur.right);
                }
                if(normal){
                    list.add(cur.val);
                }
                else{
                    list.add(0,cur.val);
                }
            }
            result.add(list);
            normal = !normal;

        }
        return result;
    }