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

import java.util.ArrayList;
import java.util.*;

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

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

    }

}
*/
// 层次遍历使用队列
// 难点在于如何划分层次：进入每一个层次之前，先统计一下队列长度
// 每层顺序不同：反转数组
// 时空复杂度：O（n）
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
    	// 初始化数组、队列、变量，加入根节点
        Queue<TreeNode> q = new LinkedList<>();
        ArrayList<ArrayList<Integer>> outlist = new ArrayList<>();
        if (pRoot == null)
            return outlist;
        q.add(pRoot);
        int num = q.size();
        boolean reverse = false;
        // 终止条件：结束上一层遍历时，队列长度为0
        while (num != 0){
            ArrayList<Integer> inlist = new ArrayList<>();
            for (int i = 0; i < num; i++){
                TreeNode node = q.poll();
                inlist.add(node.val);
                if (node.left != null)
                    q.add(node.left);
                if (node.right != null)
                    q.add(node.right);
            }
            num = q.size();
            if (reverse == true){
                reverse = false;
                Collections.reverse(inlist);
            }
            else
                reverse = true;
            outlist.add(inlist);
        }
        return outlist;
    }

}