按之字顺序打印二叉树

思路：本题是层次遍历的改进（广度优先遍历）。

1. 根为空，返回空的序列
2. 初始化一个队列，根节点入队，设置一个遍历记录当前的层数(根所在层为1)和当前层的节点的数量。
3. 当队列不为空的时候，且当前行在队列中的节点数量不为0的时候，取队头元素加入到list中，把队头的左右节点入队，当前行在队列中的节点数量-1。当当前行在队列中的元素为0时，说明此行遍历完了，把list加到result上，同时下一行的元素个数为当前队列的大小，当队列不为空时，继续循环。
4. 在把list加到result的时候，注意：当为偶数行的时候，把list中的顺序逆序。

import java.util.ArrayList;

/*
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) {
        ArrayList<ArrayList<Integer> >  result = new ArrayList<>();//存放结果
        if(pRoot ==null){
            return result;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(pRoot);
        int sum = 1;//当前层的个数
        int num = 1;//定义第几层
        while(queue.size()!=0){
            ArrayList<Integer> list = new ArrayList<>();
            while(sum>0){
                TreeNode t = queue.poll();
                list.add(t.val);
                if(t.left!=null){
                    queue.add(t.left);
                }
                if(t.right!=null){
                    queue.add(t.right);
                }
                sum--;
            }
            sum = queue.size();
            //当是偶数层的时候，对list逆序
            if(num%2 == 0){
                for(int i = 0,j = list.size() -1;i<j; i++,j--){
                    int temp = list.get(i);
                    list.set(i,list.get(j));
                    list.set(j,temp);
                }
            }
            num++;
            result.add(list);
        }
        return result;
    }

}