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

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 {
    /**
    * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
    *
    *
    * @param pRoot TreeNode类
    * @return int整型ArrayList<ArrayList<>>
    */
    public ArrayList<ArrayList<Integer>> Print (TreeNode pRoot) {
        if (pRoot == null) {
            return new ArrayList<ArrayList<Integer>>();
        }
        // write code here
        //需要采用层序遍历，利用Queue结构
        //print(pRoot);
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        //声明一个队列 queue 单向，deque 双向队列
        Queue<TreeNode> queue = new LinkedList<>();
        //先将根节点加入
        queue.offer(pRoot);
        //层，奇数 正序，偶数 反序
        int level = 1;
        while (!queue.isEmpty()) {
            ArrayList<Integer> subList = new ArrayList<>();
            int length = queue.size();
            for (int i = 0; i < length; i++) {
                //推出队列中的一个元素
                TreeNode node = queue.poll();             
                    //判断左右子节点是否存在，从头部添
                    if (node.left != null) {
                        queue.offer(node.left);
                    } 
                    if (node.right != null) {
                        queue.offer(node.right);
                    }                               
                //将值加入列表中
                subList.add(node.val);
            }
            if(level%2==0){
                //偶数反转列表
                Collections.reverse(subList);
            }
            list.add(subList);
            level++;
        }
        return list;
    }

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param pRoot TreeNode类
     * @return int整型ArrayList<ArrayList<>>
     */
    public ArrayList<ArrayList<Integer>> Print2 (TreeNode pRoot) {
        if (pRoot == null) {
            return new ArrayList<ArrayList<Integer>>();
        }
        // write code here
        //需要采用层序遍历，利用Queue结构
        //print(pRoot);
        ArrayList<ArrayList<Integer>> list = new ArrayList<>();
        //声明一个队列 queue 单向，deque 双向队列
        Deque<TreeNode> queue = new LinkedList<>();
        //先将根节点加入
        queue.offer(pRoot);
        //层，奇数 正序，偶数 反序
        int level = 1;
        while (!queue.isEmpty()) {
            ArrayList<Integer> subList = new ArrayList<>();
            int length = queue.size();
            for (int i = 0; i < length; i++) {
                //推出队列中的一个元素
                TreeNode node = null;
                if (level % 2 == 0) {
                    //是偶数,反序，从尾部推出
                    node = queue.pollLast();
                    //判断左右子节点是否存在，从头部添加,并且先右后左
                    if (node.right != null) {
                        queue.offerFirst(node.right);
                    }
                    if (node.left != null) {
                        queue.offerFirst(node.left);
                    }
                } else {
                    //奇数层正序，从头部推出
                    node = queue.pollFirst();
                    //判断左右子节点是否存在，从尾部添加
                    if (node.left != null) {
                        queue.offerLast(node.left);
                    }
                    if (node.right != null) {
                        queue.offerLast(node.right);
                    }
                }
                //将值加入列表中
                subList.add(node.val);

            }
            list.add(subList);
            level++;
        }
        return list;
    }
}

该算法核心是使用“层序遍历”法，便可实现按“层”打印出二叉树，细节上差异就是每一层从不同的方向开始打印而已

二叉树常规遍历法有三种：“前序遍历”、“中序遍历”、“后序遍历”，所谓 前、中、后 的遍历方式是根据二叉树的特征而来，一个根节点两个左右子节点，前中后 是指的根节点的遍历顺序，比如前序即为 根节点、左节点、右节点； 中序遍历即为 左节点、根节点、右节点；后序遍历即为 左节点、右节点、根节点；

而 层序遍历 的方式，即使按照 二叉树的数组结构数据的顺序的遍历方式，需要借助第三方数据结构来实现，常用的为队列，具体接口为 Queue、Deque，一个是单向队列，一个是双向队列

所以算法根据队列来实现，就有两种方式来实现

1、通过Queue 单向队列，先 offer 装入根节点，然后while 循环，取出一个节点，再次将其左右子节点装入队列中，这样一次循环就是一层的数据，以此类推，核心是判断奇偶层，如果是偶数层，通过 Collections.reverse 方法翻转列表即可

2、通过 Deque 双向列表，就不用翻转列表数据，但是需要再取和装数据时注意方向，正序列表需要 左取右入，通过 pollFirst 取，offerLast 装入；逆序列表需要右取左入，即通过 pollLast 取，offerFirst 装入；整体遍历方式和第一方式类似

补充说明：队列Queue 添加元素方法有 add 和 offer ，不同是超出容量，add会抛异常，offer放回false；取出元素方法有 poll 和 peek，不同是 poll 是取出元素并异常队列，而 peek 只是取出元素，和 poll 类似的还有 remove 方法，和 peek 类似的有 element 方法