之字形打印

本题考查树的 BFS.BFS就是一层一层的遍历，我们用队列实现。一个队列的话我们没有层次的限制，直到这个队列为空，说明我们遍历完了。但是现在我们要记录下每一层的节点。相当于问题转为给定一棵二叉树，麻烦打印一下第n层的所有节点。所以为了让每一层都有明显的分开，我们用两个队列来实现互相保存。 之字形的话无非就是要将其中一个队列反转一下顺序。

可读性来了：

public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    ArrayList<ArrayList<Integer>> res=new ArrayList<>();
    LinkedList<TreeNode> list1=new  LinkedList<>();
    LinkedList<TreeNode> list2=new  LinkedList<>();
    if(pRoot==null){
        return res;
    }
    list1.add(pRoot);
    while(!list1.isEmpty() || !list2.isEmpty()){ //循环交替互相保存遍历的节点
        if(!list1.isEmpty()){ //取出我们要的 val
            printTreeNode(res,list1,0);
        }
        while(!list1.isEmpty()){ //遍历下一层
            addList(list1,list2);
        }
        if(!list2.isEmpty()){ //取出我们要的 val
            printTreeNode(res,list2,1); 
        }
        while(!list2.isEmpty()){ //遍历下一层
            addList(list2,list1);
        }
    }
    return res;
}

public void printTreeNode(ArrayList<ArrayList<Integer>> res,LinkedList<TreeNode> list,int mode){ //好就不写代码了，原来还有 .reverse()方法，就不用遍历了
    ArrayList<Integer> listNums=new ArrayList<>();
    if(mode==0){
        for(TreeNode root:list){
            listNums.add(root.val);
        }
    }else{
        for(int i=list.size()-1;i>=0;i--){
            listNums.add(list.get(i).val);
        }
    }
    res.add(listNums);
    return ;
}


public void addList(LinkedList<TreeNode> list1,LinkedList<TreeNode> list2){
    TreeNode root=list1.removeFirst();
    if(root.left!=null){
        list2.add(root.left);
    }
    if(root.right!=null){
        list2.add(root.right);
    }
}