public ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        ArrayList<Integer> cur = new ArrayList<Integer>();
        if(root == null) return res;
        queue.offer(root);
        queue.offer(null);

        boolean flip = false;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node == null) {
                if(flip) {
                    Collections.reverse(cur);
                }
                flip = !flip;
                res.add(new ArrayList<Integer>(cur));
                cur.clear();
                if(queue.size() == 0) break;
                queue.offer(null);
            }else {
                cur.add(node.val);
                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }
        }
        return res;
    }