题解 | #二叉树的按层打印与ZigZag打印#

代码如下

import java.util.*;
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    public TreeNode(int val) {
        this.val = val;
    }
}
public class Main {

    static Map<Integer, TreeNode> cache = new HashMap<>();

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while(scanner.hasNext()) {
            int nodeNum = scanner.nextInt();
            int rootNo = scanner.nextInt();
            int n = nodeNum;
            int[][] info = new int[nodeNum][3];
            int i = 0;
            while(n > 0) {
                info[i][0] = scanner.nextInt();
                info[i][1] = scanner.nextInt();
                info[i][2] = scanner.nextInt();
                i++;
                n--;
            }
            TreeNode root = constructTree(rootNo, info);
            print(root);
            zigzagPrint(root);
        }
    }

    private static void print(TreeNode root) {
        if (root == null) {
            return;
        }
        System.out.print("Level 1 : ");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode last = root;
        TreeNode nLast = null;
        int level = 1;
        while(!queue.isEmpty()) {
            TreeNode head = queue.poll();
            System.out.print(head.val + " ");
            if (head.left != null) {
                queue.offer(head.left);
                nLast = head.left;
            }
            if (head.right != null) {
                queue.offer(head.right);
                nLast = head.right;
            }
            if (last == head) {
                System.out.println();
                level++;
                if (!queue.isEmpty()) {
                    System.out.printf("Level %d : ", level);
                }
                last = nLast;
            }
        }
    }

    private static void zigzagPrint(TreeNode root) {
        if (root == null) {
            return;
        }
        Deque<TreeNode> deque = new LinkedList<>();
        boolean orientation = true;
        int level = 1;
        deque.offer(root);
        TreeNode last = root;
        TreeNode nLast = null;
        System.out.print("Level 1 from left to right: ");
        while(!deque.isEmpty()) {
            TreeNode head = null;
            if (orientation) {
                head = deque.poll();
            } else {
                head = deque.pollLast();
            }
            System.out.print(head.val + " ");
            if (orientation) {
                if (head.left != null) {
                    deque.offer(head.left);
                    if (nLast == null) {
                        nLast = head.left;
                    }
                }
                if (head.right != null) {
                    deque.offer(head.right);
                    if (nLast == null) {
                        nLast = head.right;
                    }
                }
            } else {
                if (head.right != null) {
                    deque.offerFirst(head.right);
                    if (nLast == null) {
                        nLast = head.right;
                    }
                }
                if (head.left != null) {
                    deque.offerFirst(head.left);
                    if (nLast == null) {
                        nLast = head.left;
                    }
                }
            }


            if (last == head) {
                level++;
                last = nLast;
                System.out.println();
                if (!deque.isEmpty()) {
                    if (orientation) {
                        System.out.printf("Level %d from right to left: ", level);
                    } else {
                        System.out.printf("Level %d from left to right: ", level);
                    }
                    orientation = !orientation;
                    nLast = null;
                }
            }
        }

    }

    private static TreeNode constructTree(int rootNo,int [][] info) {
        for(int i = 0;i < info.length;i++) {
            int curNo = info[i][0];
            TreeNode curNode = getOrCacheNode(curNo);
            int leftNo = info[i][1];
            TreeNode leftNode = getOrCacheNode(leftNo);
            int rightNo = info[i][2];
            TreeNode rightNode = getOrCacheNode(rightNo);
            curNode.left = leftNode;
            curNode.right = rightNode;
        }
        return getOrCacheNode(rootNo);
    }

    private static TreeNode getOrCacheNode(int no) {
        if (no == 0) {
            return null;
        }
        TreeNode exist = cache.get(no);
        if (exist == null) {
            exist = new TreeNode(no);
            cache.put(no, exist);
        }
        return exist;
    }
}

把输入的数字存入info二维数组，constructTree方法用于构造树并返回树的根。
首先介绍按层打印的方法。
首先做判空处理，如果根空那么直接返回，什么都不打印。
如果根不空，把根入队，打印"Level 1 : ", 注意空格要与示例中相同。同时初始化层数level为1，并定义两个指针，last指向当前层最后一个元素，初始化是树根，nLast指向下一层的最后一个元素，因为现在暂且不知道，所以指向空即可。
当队列非空时循环处理，把队首元素拉出记为head，打印head的值，如果head左孩子不空，把head左孩子入队，nLast指向head左孩子，如果head右孩子不空，把head右孩子入队，nLast执行head右孩子。判断取出的元素是否已经是当前行最后一个，如果是，那么把层级数level加1，打印换行，之后再打印"Level 下一行号",并把当前行最后一个元素指针last指向nLast,nLast指向null或者保持不变均可。这里有一个小坑，如果已经扫到当前行最后一个元素且队列已经空了，那么是不应该再进入下一行并打印Level的，所以打印前要先判断队列非空。
接下来介绍zigzag打印的方法。
有了顺序打印的基础，zigzag只需要把队列变为双端队列，定义一个orientation的boolean类型变量表示当前行是从左到右还是从右到左，之后根据这个左右顺序不同来操作nLast指针移动和入队方式即可。
定义orientation为true表示当前行为从左向右。先做root判空，如果非空那么尾插(尾部插入，offer()或者offerLast())入队。首先直接打印"Level 1 from left to right: ",如果队列非空执行循环，如果检测到当前行方向是从左到右，那么就头弹(头部弹出，poll()或者pollFirst())记为head,否则尾弹(尾部弹出,pollLast())同样记为head，打印head对应的值。如果从左到右，那么就先取左孩子，再取右孩子；如果从右到左，就先取右孩子，再取左孩子。再从左到右取的过程中，均采用尾插。且只有nLast非空时才做赋值。如果是从右到左的过程，那么均采用头插法，nLast指针同样只有空时才做赋值。检测到当前节点是当前层的左后一个时，根据方向分别打印不同的串，把层级加一并改变方向，注意nLast一定要置空，否则在循环里就不动了。