二叉树的按层打印与ZigZag打印

题目：二叉树的按层打印与ZigZag打印

《程序员代码面试指南》第39题 P132 难度：尉★★☆☆

按层打印原本是非常基础的内容，对二叉树做简单的宽度优先遍历即可。不过本题有额外的要求，即同一层的节点必须打印在同一行上，并且要求输出行号。

本题使用了2个Node类型的变量，last和nLast。分别表示当前行的最右节点与下一行的最右节点。

如果发现遍历到的节点正好等于last，则说明应该换行。换行后，令last=nLast。

对于nLast的更新，只要让它一直跟踪最新加入队列的节点即可。易知，最新加入的节点一定是下一行的最右节点。

public void printByLevel(Node head) {
    if (head == null) {
        return;
    }
    Queue<Node> queue = new LinkedList<Node>();
    int level = 1;
    Node last = head;
    Node nLast = null;
    queue.offer(head);
    System.out.print("Level " + (level++) + " : ");
    while (!queue.isEmpty()) {
        head = queue.poll();
        System.out.print(head.value + " ");
        if (head.left != null) {
            queue.offer(head.left);
            nLast = head.left;
        }
        if (head.right != null) {
            queue.offer(head.right);
            nLast = head.right;
        }
        if (head == last && !queue.isEmpty()) {
            System.out.print("\nLevel " + (level++) + " : ");
            last = nLast;
        }
    }
    System.out.println();
}

对于ZigZag打印，最终的结果也只是偶数行倒序输出而已，不过实现起来需要一个双端队列。

这里需要额外说明一下，不能使用2个ArrayList或是2个Stack来实现，底层都是动态数组，当元素数量达到一定规模时将发生扩容，扩容的时间复杂度为O(N)。用该数据结构来实现，不够“纯粹”和“干净”。Stack最好平时也尽量减少使用，详见：为什么JDK建议使用ArrayDeque实现栈

使用双端队列实现ZigZag打印时，需要注意：

1. 如果是从左到右的过程，那么一律从dq的头部弹出节点。如果当前节点有孩子节点，则让孩子节点以先左后右的顺序从尾部加入dq；
2. 如果是从右到左的过程，那么一律从dq的尾部弹出节点。如果当前节点有孩子节点，则让孩子节点以先右后左的顺序从头部加入dq。

当遍历到的节点刚好等于last，则进行上面2种打印的切换。

不过如何确定下一层的最后节点呢？不难发现，下一层最后打印的节点就是当前层有孩子节点的节点中最先加入dq的节点。

public void printByZigZag(Node head) {
    if (head == null) {
        return;
    }
    Deque<Node> dq = new LinkedList<Node>();
    int level = 1;
    boolean lr = true;
    Node last = head;
    Node nLast = null;
    dq.offerFirst(head);
    pringLevelAndOrientation(level++, lr);
    while (!dq.isEmpty()) {
        if (lr) {
            head = dq.pollFirst();
            if (head.left != null) {
                nLast = nLast == null ? head.left : nLast;
                dq.offerLast(head.left);
            }
            if (head.right != null) {
                nLast = nLast == null ? head.right : nLast;
                dq.offerLast(head.right);
            }
        } else {
            head = dq.pollLast();
            if (head.right != null) {
                nLast = nLast == null ? head.right : nLast;
                dq.offerFirst(head.right);
            }
            if (head.left != null) {
                nLast = nLast == null ? head.left : nLast;
                dq.offerFirst(head.left);
            }
        }
        System.out.print(head.value + " ");
        if (head == last && !dq.isEmpty()) {
            lr = !lr;
            last = nLast;
            nLast = null;
            System.out.println();
            pringLevelAndOrientation(level++, lr);
        }
    }
    System.out.println();
}

public void pringLevelAndOrientation(int level, boolean lr) {
    System.out.print("Level " + level + " from ");
    System.out.print(lr ? "left to right: " : "right to left: ");
}