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

import java.util.*;

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node (int val) {
        this.val = val;
    }
}

public class Main {
    public static void main (String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        Node head = constructTree(sc, n);
        printLevels(head);
        printZigzag(head);
    }

    public static Node constructTree (Scanner sc, int n) {
        HashMap<Integer, Node> map = new HashMap<>();
        int rootVal = sc.nextInt();
        Node root = new Node(rootVal);
        map.put(rootVal, root);
        for (int i = 0; i < n; i++) {
            int nodeVal = sc.nextInt();
            int leftVal = sc.nextInt();
            int rightVal = sc.nextInt();
            if (map.containsKey(nodeVal)) {
                Node tmpNode = map.get(nodeVal);
                Node leftNode = leftVal == 0 ? null : new Node(leftVal);
                Node rightNode = rightVal == 0 ? null : new Node(rightVal);
                tmpNode.left = leftNode;
                tmpNode.right = rightNode;
                if (leftVal != 0)
                    map.put(leftVal, leftNode);
                if (rightVal != 0)
                    map.put(rightVal, rightNode);
            }
        }
        return root;
    }

    //问题在于何时换行，只需知道何时到了一个level的结尾即可，用两个变量last与nlast记录
    //本行结尾与下一行结尾，每次让last = nlast。而nlast则一直跟踪记录宽度优先的队列中
    //新加入的数即可。
    public static void printLevels(Node head) {
        if (head == null) {
            return;
        }
        Node last = head;
        Node nlast = null;
        Queue<Node> q = new LinkedList<Node>();
        q.offer(head);
        int level = 1;
        System.out.print("Level " + (level++) + " : ");
        while (!q.isEmpty()) {
            Node cur = q.poll();
            System.out.print(cur.val + " ");
            if (cur.left != null) {
                q.offer(cur.left);
                nlast = cur.left;
            }
            if (cur.right != null) {
                q.offer(cur.right);
                nlast = cur.right;
            }
            if (cur == last && !q.isEmpty()) {
                System.out.println();
                System.out.print("Level " + (level++) + " : ");
                last = nlast;
            }
        }
        System.out.println();
    }

    public static void printZigzag (Node head) {
        if (head == null)
            return;
        Node cur = head;
        Node last = head;
        Node nlast = null;
        Deque<Node> dq = new LinkedList<Node>();
        dq.offerFirst(cur);
        int level = 1;
        boolean fLtR = true;
        System.out.print("Level " + (level++) + " from left to right: " );
        while (!dq.isEmpty()) {
            if (fLtR) {
                head = dq.pollFirst();
                if (head.left != null) {
                    dq.offerLast(head.left);
                    nlast = nlast == null ? head.left : nlast;
                }
                if (head.right != null) {
                    dq.offerLast(head.right);
                    nlast = nlast == null ? head.right : nlast;
                }
            }
            else {
                head = dq.pollLast();
                if (head.right != null) {
                    dq.offerFirst(head.right);
                    nlast = nlast == null ? head.right : nlast;
                }
                if (head.left != null) {
                    dq.offerFirst(head.left);
                    nlast = nlast == null ? head.left : nlast;
                }
            }
            System.out.print(head.val + " ");
            if (last == head && !dq.isEmpty()) {
                System.out.println();
                fLtR = !fLtR;
                if (fLtR)
                    System.out.print("Level " + (level++) + " from left to right: " );
                else
                    System.out.print("Level " + (level++) + " from right to left: " );
                last = nlast;
                nlast = null;
            }
        }
        System.out.println();
    }
}