剑指Offer59 之字形遍历树

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

1. 设置一个顺序flag = true
2. flag == true时候从左往右，添加
3. flag == flase时候从右往左，从右往左添加
4. 一层遍历完成后将队列reverse，并

    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> lists = new ArrayList<>(); // 最后answer
        if(pRoot == null) return lists;
        Queue<TreeNode> queue = new LinkedList<>(); // 当前层
        List<TreeNode> nexts = new LinkedList<>(); // 下一层
        queue.offer(pRoot); // 初始化
        boolean flag = true; // 先添加left，再添加right，否则相反
        TreeNode p = null;
        
        while(!queue.isEmpty()){
            ArrayList<Integer> list = new ArrayList<>();
            while(!queue.isEmpty()){
                p = queue.poll();
                if(p == null) continue;
                list.add(p.val);
                if(flag){
                    nexts.add(p.left);
                    nexts.add(p.right);
                } else{
                    nexts.add(p.right);
                    nexts.add(p.left);
                }
            }
            if(!list.isEmpty()) lists.add(list);
            Collections.reverse(nexts); // 将将要遍历的队列reverse
            queue.addAll(nexts);
            nexts.clear();
            flag = !flag;
        }
        return lists;
    }

存在的问题：

1. 每一次都需要reverse操作，耗费时间
2. 每一次都需要addAll()操作，对空间和时间需求都比较高

改进

使用双Stack，分别记录奇数层和偶数层。