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

import java.util.ArrayList;

import java.util.ArrayDeque;

public class Solution {

public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    ArrayList<ArrayList<Integer>> Arr = new ArrayList<ArrayList<Integer>>();
    if(pRoot==null)
        return Arr;
    //层序遍历，想到队列
    ArrayDeque<TreeNode> dq = new ArrayDeque<>();
    dq.addLast(pRoot);
    int layer=1;//记录当前遍历的层数，奇数层从左到右遍历，偶数层反之
    while(!dq.isEmpty()){
        int curSize = dq.size();//当前层的节点个数
        ArrayList<Integer> arr = new ArrayList<Integer>();
        if((layer++)%2==1){
            while(curSize-->0){
                TreeNode node = dq.pollFirst(); //从队列头出节点
                arr.add(node.val);
                //在队列尾添加节点，先添加左节点，再添加右节点
                if(node.left!=null) dq.addLast(node.left);
                if(node.right!=null) dq.addLast(node.right);
            }
        } else {
            while(curSize-->0){
                TreeNode node = dq.pollLast();//从队列尾出节点
                arr.add(node.val);
                //在队列头添加节点，因为新节点添加后原来的节点会往后移，
                //所以需要先添加右节点，再添加左节点
                if(node.right!=null) dq.addFirst(node.right);
                if(node.left!=null) dq.addFirst(node.left);
            }
        }
        Arr.add(arr);
    }
    return Arr;
}

}