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

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) {
        ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();//定义用来维护的数组
        queue.offer(pRoot);//存入二叉树的头节点
        int sum = 1;//用来记载某一层的节点个数
        int num = 1;//用来记载层数
        while(pRoot != null && !queue.isEmpty()){
            ArrayList<Integer> son = new ArrayList<>();//定义子列表
            int temp = 0;//临时变量,一定注意初始值为0，存入左右孩子的时候加1，内循环结束赋给sum。用来统计下一层节点个数
            while(sum > 0){
                TreeNode node = queue.poll();//取出队首并且删除。
                son.add(node.val);
                if(node.left != null){
                    queue.offer(node.left);//存入左右子树，经典的BFS维护队列方式
                    temp++;//下一层节点放入，temp加1.最终temp为下一层节点个数
                }
                if(node.right != null){
                    queue.offer(node.right);
                    temp++;
                }
                sum--;//一开始第一层减一次就内循环结束。后来sum为2了就可以两次.....
            }
            sum = temp;
            if(num % 2 == 0){//如果是偶数层，还要倒置子列表的元素。
                Collections.reverse(son);//直接调用集合类的倒置方法就可以。
            }
            num++;//结束了倒置判断了就要把层数加一
            if(son != null){
                ans.add(son);
            }
        }
        return ans;
    }
}

在经典BFS的基础上，添加了分层，判断是否为偶数层等功能。难度实际上相当于leetcode普通题