public static ArrayList<ArrayList<Integer>> zigzagLevelOrder(TreeNode root) {
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (root == null) {
            return res;
        }
        LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
        queue.addLast(root);
        int level = 0;

        while (!queue.isEmpty()) {
            LinkedList<TreeNode> tmp = new LinkedList<TreeNode>();
            ArrayList<Integer> list = new ArrayList<Integer>();

            for (int i = 0; i < queue.size(); i++) {
                TreeNode node = queue.get(i);
                list.add(node.val);

                if (node.left != null) {
                    tmp.addLast(node.left);
                }

                if (node.right != null) {
                    tmp.addLast(node.right);
                }
            }

            if (level % 2 == 1) {
                Collections.reverse(list);
            }

            level++;
            queue = tmp;
            res.add(list);
        }

        return res;
    }