public ArrayList<ArrayList<Integer>> zigzagLevelOrder_lint(TreeNode root) {
        // write your code here
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        if (root == null)
            return res;
        boolean left = true;
        ArrayList<TreeNode> queue = new ArrayList<TreeNode>();
        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; ++i) {
                TreeNode cur = queue.get(i);
                if (cur.left != null)
                    queue.add(cur.left);
                if (cur.right != null)
                    queue.add(cur.right);
            }
            ArrayList<Integer> temp = new ArrayList<Integer>();
            if (left) {
                while (size-- > 0) {
                    temp.add(queue.get(0).val);
                    queue.remove(0);
                }
            } else {
                while (size-- > 0) {
                    temp.add(queue.get(size).val);
                    queue.remove(size);
                }
            }
            res.add(temp);
            left = !left;
        }
        return res;
    }