利用队列

/*
思路：利用队列，bfs。将队列中一层元素的孩子都一次性添加到队列中。然后根据标志输出正反序
*/
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        if(pRoot == null)    return new ArrayList<>(0);    //返回空的list
        Queue<TreeNode> queue = new LinkedList<>();
        ArrayList<ArrayList<Integer>> arraylist = new ArrayList<ArrayList<Integer>>();
        queue.add(pRoot);
        boolean flag = false;    //打印标志，false正着添加，true倒着添加
        while(!queue.isEmpty()){
            int size = queue.size();    //表示一层的宽度，这个值到0之后，进入下一层
            //保存一层的结点数组
            ArrayList<Integer> list = new ArrayList<>(size + 1);
            for(; size>0; --size){
                TreeNode node = queue.poll();
                if(node.left != null)    queue.add(node.left);
                if(node.right != null)    queue.add(node.right);
                //判断一下标志，决定正序插入还是反序
                if(!flag){
                    //正序
                    list.add(node.val);
                }else{
                    //反序
                    list.add(0, node.val);    //这个能倒序插入值
                }

            }
            //这一层结束，变换标志，添加进结果集
            if(flag == true){
                flag = false;
            }else{
                flag = true;
            }
            arraylist.add(list);
        }
        return arraylist;
    }
}