按之字形顺序打印二叉树

1.题目：
请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
2.思路：
方法一：与题目《把二叉树打印成多行》，《从上往下打印二叉树》类似，都是树的广度优先遍历(BFS),或者说是层序遍历；只不过这道题增加打印的规则，那么我们可以在以前代码的基础上增加一点约束就行：

• list.add(T): 按照索引顺序从小到大依次添加
• list.add(index, T): 将元素插入index位置，index索引后的元素依次后移,这就完成了每一行元素的倒序，或者使用Collection.reverse()方法倒序也可以

  public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();//返回嵌套的答案
        Queue<TreeNode> queue=new LinkedList<>();
        if(pRoot==null){
            return res;
        }
        queue.offer(pRoot);
        boolean reverse=false;//设置反转标志位
        while(!queue.isEmpty()){
            int count=queue.size();//记录树当前层的节点数
            ArrayList<Integer> list=new ArrayList<>();//每一层都需要一个新的集合来存储
            while(count>0){
                TreeNode cur=queue.poll();
                if(reverse){//如果需要反转，则从右往左输出
                    list.add(0,cur.val);
                }else{//不需要反转，从左往右输出
                    list.add(cur.val);
                }
                if(cur.left!=null) queue.offer(cur.left);
                if(cur.right!=null) queue.offer(cur.right);
                count--;
            }
            res.add(list);
            reverse=!reverse;//进入下一层之前翻转
        }
        return res;
    }
  }

  方法二：用栈的思想，这里参考题解区的大佬们的思路
  

  public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res=new ArrayList<>();
        if(pRoot==null) return res;
        Stack<TreeNode> S1=new Stack<>();//从左往右输出层
        Stack<TreeNode> S2=new Stack<>();//从右往左输出层
        S1.push(pRoot);
        while(!S1.isEmpty()||!S2.isEmpty()){
            ArrayList<Integer> list=new ArrayList<>();//存储当前层的输出节点
            while(!S1.isEmpty()){//左=》右输出层
                pRoot=S1.pop();
                if(pRoot!=null){
                list.add(pRoot.val);
                if(pRoot.left!=null) S2.push(pRoot.left);//此处的顺序与下面的顺序刚好相反
                if(pRoot.right!=null) S2.push(pRoot.right);
                }
              }
            if(!list.isEmpty()){
            res.add(list);
            }
            list=new ArrayList<>();
            while(!S2.isEmpty()){//右=》左输出层
                pRoot=S2.pop();
                if(pRoot!=null){
                list.add(pRoot.val);
                if(pRoot.right!=null) S1.push(pRoot.right);
                if(pRoot.left!=null) S1.push(pRoot.left);
                }
            }
            if(!list.isEmpty()){//此处一定要判空，不然空集合也会加入到答案中
            res.add(list);
            }
       }
       return res;
    }
  }
  

```