OptimalSolution(2)--二叉树问题（1）遍历与查找问题

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

　　1.按层打印：

      1                   Level 1 : 1
    /    　　　　　　　　　　
  2       3　　　　　　　　　Level 2 : 2 3　
 /       /   　　　　　　　　　
4      5     6　　　　　　　Level 3 : 4 5 6
       /   
     7     8        　　  Level 4 : 7 8

　　题目中要求同一层的节点必须打印在一行上，并且要求输出行号。这就需要我们在原来的广度优先遍历基础上，必须要搞明白的是什么时候要换行。

　　解决方法：使用node类型的变量last便是正在打印的当前行的最右节点，nLast便是下一行的最右节点。假设每一层都做从左到右的宽度优先遍历，如果发现遍历的节点等于last，说明该换行了。换行之后令last=nLast，就可以继续下一行的打印过程，直到所有的节点都打印完。为了更新nLast，只需要让nLast一直跟踪记录宽度优先遍历队列中的最新加入的节点即可。这是因为最新加入队列的节点一定是目前已经发现的下一行的最右结点。所以在当前行打印完时，nLast一定是下一行所有节点中的最右节点。

　　分析执行过程：

初始时，last=1，nLast=null，1入队列，此时：1 → 出的方向
1出队列，打印第一行，此时：→ ，2入队列，3入队列，nLast=3，此时：3 2 →，root == last，换行，last=3
2出队列，root=2，打印2，4入队列，nLast=4，此时 4 3 → 
3出队列，root=3，打印3，5入队列，6入队列，nLast=6，此时6 5 4 → ，root==last，换行，last=6
...

　　代码实现：

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

　　2.ZigZag打印

      1                    Level 1 from left to right ： 1
    /    　　　　　　　　　　
  2       3　　　　　　　　　 Level 2 from right to left ： 3 2
 /       /   　　　　　　　　　
4      5     6　　　　　　　 Level 3 from left to right ：4 5 6
       /   
     7     8        　　   Level 4 from right to left ： 8 7

　　第一种思路：使用两个ArrayList结构list1和list2，用list1去收集当前层的节点，然后从左到右打印当前层，接着把当前层的孩子节点放进list2，并从右到左打印，接下来再把list2的所有节点的孩子节点放入list1，如此反复。这种思路不好的原因是因为：ArrayList结构为动态数组，在这个结构中，当元素数量到一定规模时将发生扩容操作，扩容操作的时间复杂度为O(N)是比较高的，这个结构增加和删除元素的时间复杂度也较高。总之，用这个结构对本地来讲数据结构不够纯粹和干净，所以最好不要使用。

　　第二种思路：使用Java中的LinkedList结构，这个结构底层的实现就是非常纯粹的双端队列结构。这道题可以使用双端队列来解决。也就是（1）如果是从左到右的过程，那么一律从双端队列的头部弹出节点，如果弹出的节点没有孩子节点，当然不用放入任何节点到双端队列中；如果当前节点有孩子节点，先让左孩子从尾部进入双端队列，然后让右孩子从尾部进入双端队列。（2）如果是从右到左的过程，那么一律从双端队列的尾部弹出节点，如果弹出的节点没有孩子节点，当然不用放入任何节点到双端队列中；如果当前节点有孩子节点，先让右孩子从头部进入双端队列，然后再让左孩子从头部进入双端队列中。（3）如何确定切换（1）和（2）的时机，其实还是如何确定每一层最后一个节点的问题，原理就是，下一层最后打印的节点是当前层有孩子的节点的孩子节点中最先进入双端队列的节点。

　　需要注意的问题：1.nLast = nLast == null ? root.left : nLast;是选择当前层的所有孩子中第一个进入deque的那个孩子，就是下一层最后打印的孩子，2.在打印完当前层后，执行完last = nLast; 这条代码的后面，必须加上nLast = null;用来清空nLast，否则将输出不符合要求的内容。

    public void printByZigZag(Node root) {
        if (root == null) return;
        Deque<Node> deque = new LinkedList<>();
        int level = 1;
        boolean lr = true;    // 一开始从左到右
        Node last = root;
        Node nLast = null;
        deque.offerFirst(root);
        printLevelAndOrientation(level++, lr);
        while (!deque.isEmpty()) {
            if (lr) {                                // 从左到右的过程
                root = deque.pollFirst();            // 头部弹出节点
                if (root.left != null) {
                    nLast = nLast == null ? root.left : nLast;
                    deque.offerLast(root.left);        // 左孩子先从尾部进入
                }
                if (root.right != null) {
                    nLast = nLast == null ? root.right : nLast;
                    deque.offerLast(root.right);    // 右孩子后从尾部进入
                }
            } else {                                // 从右到左的过程    
                root = deque.pollLast();            // 尾部弹出节点
                if (root.right != null) {
                    nLast = nLast == null ? root.right : nLast;
                    deque.offerFirst(root.right);    // 右孩子先从头部进入
                }
                if (root.left != null) {
                    nLast = nLast == null ? root.left : nLast;
                    deque.offerFirst(root.left);    // 左孩子后从头部进入
                }
            }
            System.out.print(root.val + " ");
            if (root == last && !deque.isEmpty()) {
                lr = !lr;
                last = nLast;
                nLast = null;
                System.out.println();
                printLevelAndOrientation(level++, lr);
            }
        }
    }
    
    private void printLevelAndOrientation(int level, boolean lr) {
        System.out.print("Level " + level + " from ");
        System.out.print(lr ? "left to right : " : "right to left : ");
    }

　　分析执行过程：

初始时，last=1，nLast=null，1入队列，此时：（尾） 1  （头）
第一层，从左到右，nLast=2，2从尾部入队列，3从尾部入队列，此时：（尾） 3 2 （头），root=last，此时打印第一层，last=2，nLast=null
第二层，从右到左，3从尾部先出队列，root=3，nLast=6，6从头部入队列，5从头部入队列，此时：（尾）2 6 5（头）
第二层，从右到左，2从尾部先出队列，root=2，4从头部入队列，此时：（尾） 6 5 4 （头），root=last，此时第二层打印完毕，last=6，nLast=null
第三层，从左到右，4从头部出队列，root=4，此时：（尾）6 5 （头）
第三层，从左到右，5从头部出队列，root=5，nLast=7，7从尾部入队列，8从尾部入队列，此时：（尾）8 7 6 （头）
第三层，从左到右，6从头部出队列，root=6，此时：（尾）8 7 （头），root=last，第三层打印完毕，last=7，nLast=null
...

　　二、