按之字形顺序打印二叉树，利用层次遍历（广度优先遍历的思想）

/*
public class TreeNode {
    int val = 0;
    TreeNode left = null;
    TreeNode right = null;

    public TreeNode(int val) {
        this.val = val;

    }

}
*/

import   java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        //队列（先进先出）
        LinkedList<TreeNode>  queue=new  LinkedList<TreeNode>();
        //存放结果
        ArrayList<ArrayList<Integer>>  result=new  ArrayList<>();
        //判断头结点是否为null
        if(pRoot==null){
            return result;
        }
        //将节点放入队列中
        queue.add(pRoot);
        //标志位（改变List结合中添加元素的顺序）
        Boolean  blog=true;
        //当队列不为空时，遍历输出结点
        while(!queue.isEmpty()){
            //计算出当前循环,队列中元素的数目
            int size=queue.size();
            //存放当前层的元素（根据标志位blog）
            ArrayList<Integer>  branchResult=new  ArrayList<Integer>();
            //将当前层的元素依次弹出队列，并把它的不为空的左右子节点加入队列
            while(size>0){
                //当前层元素依次弹出队列
                TreeNode node=queue.poll();
                //根据标志位blog将当前层元素放入branchResult集合中
                if(blog){
                    branchResult.add(node.val);
                }else{
                    //每次都将元素放入索引为0的位置，原来的元素依次后移
                    branchResult.add(0,node.val);
                }
                //左结点存在则入队
                if(node.left!=null){
                    queue.add(node.left);
                }
                //右节点存在则入队
                if(node.right!=null){
                    queue.add(node.right);
                }
                //记录当前循环还剩的元素个数
                size--;
            }
            //将当前层的元素放入result集合中
            result.add(branchResult);
            //每循环一次，就改变标志位的状态
            blog=!blog;
        }
        //返回结果
        return result;
    }

}