题解 | #按之字形顺序打印二叉树#

该题可以使用队列来完成，与普通的层序遍历不一样，之形层序遍历需要新加两个变量，其一是level表示当前层数，其二是last表示当前层次最后一个节点。每次遍历到最后一个节点时，把层数加1，如果层数是奇数，则直接把当前层次的结果加入res，如果层数是偶数，把当前层次的节点序列逆转即可。事件复杂度O(n)遍历了树，空间复杂度O(n)

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        int rear = 0;//队尾
        int front = 0;//队头
        int last = 1;//每层的最后一个节点
        int level = 1;//表示当前遍历的层次
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();//返回结果
        ArrayList<Integer> layerlist = new ArrayList<Integer>();//当前层次的元素
        ArrayList<TreeNode> list = new ArrayList<TreeNode>();//队列
        if(pRoot==null)return res;
        list.add(pRoot);
        rear++;
        while(rear!=front){
            TreeNode p = list.get(front++);
            layerlist.add(p.val);
            if(p.left!=null){
                list.add(p.left);
                rear++;
            }
            if(p.right!=null){
                list.add(p.right);
                rear++;
            }
            if(front == last){
                if(level%2==0){
                     Collections.reverse(layerlist);//偶数层次的元素直接逆转
                }
                res.add((ArrayList<Integer>)layerlist.clone());
                layerlist.clear();
                last = rear;
                level++;
            }
        }
        return res;
    }

}