ac

给定一颗二叉树，分别实现按层和 ZigZag 打印二叉树。
ZigZag遍历: 意思是第一层从左到右遍历，第二层从右到左遍历，依次类推。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class TreeNode{
    TreeNode left;
    TreeNode right;
    int val;

    public TreeNode(int val) {
        this.val = val;
        left = null;
        right = null;
    }
}


public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static long mod = (long)Math.pow(2,29);

    public static void main(String[] args) throws Exception{
        String line;
        String[] strArr;
        line = reader.readLine();
        strArr = line.split(" ");
        int n = Integer.valueOf(strArr[0]);
        int rootVal = Integer.valueOf(strArr[1]);
        Map<Integer, TreeNode> mp = new HashMap<>(n);
        for (int i = 0; i < n; i++) {
            line = reader.readLine();
            strArr = line.split(" ");
            int val = Integer.valueOf(strArr[0]);
            int leftVal = Integer.valueOf(strArr[1]);
            int rightVal = Integer.valueOf(strArr[2]);

            if(!mp.containsKey(val)){
                mp.put(val, new TreeNode(val));
            }
            if(leftVal != 0){
                if(!mp.containsKey(leftVal)){
                    mp.put(leftVal, new TreeNode(leftVal));
                }
                mp.get(val).left = mp.get(leftVal);
            }
            if(rightVal != 0){
                if(!mp.containsKey(rightVal)){
                    mp.put(rightVal, new TreeNode(rightVal));
                }
                mp.get(val).right = mp.get(rightVal);
            }
        }
        TreeNode root = mp.get(rootVal);
        print(root);
        printZigZag(root);
    }

    static void print(TreeNode root){
        Queue<TreeNode> que = new LinkedList<>();
        Queue<Integer> queC = new LinkedList<>();
        que.offer(root);
        queC.offer(1);
        int lastLevel = 0;
        while (!que.isEmpty()) {
            TreeNode node = que.poll();
            int ceng = queC.poll();
            if(ceng != lastLevel){
                if(lastLevel != 0) {
                    System.out.println();
                }
                lastLevel = ceng;
                System.out.print(String.format("Level %d : ", ceng));
                System.out.print(node.val);
            }else {
                System.out.print(" " + node.val);
            }
            if (node.left != null) {
                que.offer(node.left);
                queC.offer(ceng + 1);
            }
            if (node.right != null) {
                que.offer(node.right);
                queC.offer(ceng + 1);
            }
        }
        System.out.println();
    }

    static void printZigZag(TreeNode root){
        Deque<TreeNode> deque = new LinkedList<>();
        Deque<TreeNode> dequeNext = new LinkedList<>();
        deque.addFirst(root);
        boolean dir = true;
        int level = 1;
        while (!deque.isEmpty() || !dequeNext.isEmpty()) {
            if(dir){
                printTmp(level, dir);
                while (!deque.isEmpty()){
                    TreeNode node = deque.pollFirst();
                    System.out.print(" " + node.val);
                    if(node.left != null){
                        dequeNext.addLast(node.left);
                    }
                    if(node.right != null){
                        dequeNext.addLast(node.right);
                    }
                }
                System.out.println();
            }else {
                printTmp(level, dir);
                while (!dequeNext.isEmpty()){
                    TreeNode node = dequeNext.pollLast();
                    System.out.print(" " + node.val);
                    if(node.right != null){
                        deque.addFirst(node.right);
                    }
                    if(node.left != null){
                        deque.addFirst(node.left);
                    }
                }
                System.out.println();
            }
            dir = !dir;
            level ++;
        }
    }

    static void printTmp(int level, boolean dir){
        if(dir){
            System.out.print(String.format("Level %d from left to right:", level));
        }else {
            System.out.print(String.format("Level %d from right to left:", level));
        }
    }
}
/*
       1
    /     \
   2       3
  /       / \
 4       5   6
        / \
       7   8
1
2 3 同尾部一次取 3 2， 并从头步插入
4 5 6 从头步取，同尾部插入
7 8 在从尾部取出来
 */


/*
8 1
1 2 3
2 4 0
4 0 0
3 5 6
5 7 8
6 0 0
7 0 0
8 0 0

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

*/