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

import java.util.*;

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

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

}

} */ public class Solution {

public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    //特殊情况，pHead为空
    if(pRoot == null){
        return new ArrayList();
    }
    //用来装同一行所有节点的队列
    Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
    //根据题目要求设置链表
    ArrayList<ArrayList<Integer> > valList = new ArrayList<ArrayList<Integer>>();
    nodeQueue.add(pRoot);
    int level = 1; //初始树的深度为1，判断是否反转
    //广度优先过程BFS
    while(!nodeQueue.isEmpty()){
        //非空节点个数
        int size = nodeQueue.size();
        //用于接收数据和反转的的临时列表
        ArrayList<Integer> tmpList = new ArrayList<Integer>();
        for(int i = 0; i < size; i++){
            //得到节点，将val加入临时列表tmpList
            TreeNode tn = nodeQueue.poll();
            tmpList.add(tn.val);
            //将节点的非空子节点加入队列
            if(tn.left != null){
                nodeQueue.offer(tn.left);
            }
            if(tn.right != null){
                nodeQueue.offer(tn.right);
            }
            
        }
        //根据深度判断是否反转
        if(level % 2 == 0){
            Collections.reverse(tmpList);
        }
        //得到当前深度的结果，深度level++
        valList.add(tmpList);
        level++;
    }
    return valList;
}

}