59-按之字形顺序打印⼆叉树

题⽬描述

请实现⼀个函数按照之字形打印⼆叉树，即第⼀⾏按照从左到右的顺序打印，第⼆层按照从右⾄左的顺序打印，第三⾏按照从左到右的顺序打印，其他⾏以此类推。

示例1
输⼊：{8,6,10,5,7,9,11}
返回值：[[8],[10,6],[5,7,9,11]]

思路及解答

1. 借助双向链表，初始化⼀个添加⽅向 boolean 值，先将根节点添加进去：
2. 获取 list ⾥⾯剩下的元素的个数，挨个取出就是⼀层，取出的时候，如果 reverse 为 true ，则往链表的第 0 个索引位置添加，否则直接在后⾯添加，然后判断每⼀个取出来的节点的左右节点是不是为空，不为空则加⼊链表。
3. 每⼀层处理完之后，将 list 加⼊结果集中，然后翻转 reverse 的值，继续判断 list 是不是为空，执⾏第⼆步循环。

public class Solution {
    public ArrayList < ArrayList < Integer >> Print(TreeNode pRoot) {
        LinkedList < TreeNode > nodes = new LinkedList < > ();
        ArrayList < ArrayList < Integer >> results = new ArrayList();
        boolean reverse = true;
        if (pRoot != null) {
            nodes.add(pRoot);
            while (!nodes.isEmpty()) {
                ArrayList < Integer > integers = new ArrayList();
                int size = nodes.size();
                for (int i = 0; i < size; i++) {
                    TreeNode node = nodes.poll();
                    if (reverse) {
                        integers.add(node.val);
                    } else {
                        integers.add(0, node.val);
                    }
                    if (node.left != null) {
                        nodes.offer(node.left);
                    }
                    if (node.right != null) {
                        nodes.offer(node.right);
                    }
                }
                if (integers.size() != 0) {
                    results.add(integers);
                }
                reverse = !reverse;
            }
        }
        return results;
    }
}

空间复杂度由于借助了额外的 list ，为 O(n) ，时间复杂度上，由于每个节点进⼊队列⼜出来，为 O(2n) ，也是 O(n) 。