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

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Queue;
import java.util.Deque;
import java.util.LinkedList;


public class Main {
    /**
     * 测试用例：（ 注意官方给的输入数据有问题，更正后如下）
     * 8 1
     * 1 2 3
     * 2 4 0
     * 4 0 0
     * 3 5 6
     * 5 7 8
     * 7 0 0
     * 8 0 0
     * 6 0 0
     */
    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        String[] firstRow = in.readLine().split(" ");
        int row = Integer.parseInt(firstRow[0]);
        TreeNode<String> root = TreeUtils.makeBinaryTreeByInput(in);

        //按层打印
        PrintByLevel.printByLevel2(root);

        System.out.println();

        //之字形打印
        PrintByZigZag.printByZigZag(root);

    }

}



/**
 * @描述：  按Z字形按层打印二叉树的节点
 * @思路：只使用一个双端队列dq
 * 定义规则：
 * 规则1：若顺序是从左到右，从dq的头部弹出节点node；若node有孩子，以“先左后右”的形式从尾部进入dq.
 * 规则2：若顺序是从右到左，从dq的尾部弹出节点node；若node有孩子，以“先右后左”的形式从头部进入dq.
 * 确定规则1和规则2转换时机：（实质是一个确定每一层最后一个节点的问题）
 * 经总结发现：**下一层最后打印的节点 == 当前层有孩子节点中最先进入dq的节点 **
 * @复杂度：
 * @链接：
 */
class PrintByZigZag {

    public static <T> void printByZigZag(TreeNode<T> root) {
        Deque<TreeNode<T>> queue =  new LinkedList<>();
        boolean isLeft = true;
        TreeNode last = root;
        TreeNode nlast = null;
        int level = 1;

        queue.add(root);
        pringLevelAndOrientation(level++, isLeft);

        while (!queue.isEmpty()) {
            TreeNode curr = null;
            if (isLeft) {
                curr = queue.pollFirst();
                if (curr.left != null) {
                    queue.addLast(curr.left);
                    nlast = nlast == null ? curr.left : nlast;
                }
                if (curr.right != null) {
                    queue.addLast(curr.right);
                    nlast = nlast == null ? curr.right : nlast;
                }
            } else {
                curr = queue.pollLast();
                if (curr.right != null) {
                    queue.addFirst(curr.right);
                    nlast = nlast == null ? curr.right : nlast;
                }
                if (curr.left != null) {
                    queue.addFirst(curr.left);
                    nlast = nlast == null ? curr.left : nlast;
                }
            }
            System.out.print(curr.value + " ");

            //换行时刻(注：其中!queue.isEmpty()判断只是为了打印好看,可忽略)
            if (curr == last && !queue.isEmpty()) {
                last = nlast;
                nlast = null;
                isLeft = !isLeft;

                System.out.println();
                pringLevelAndOrientation(level++, isLeft);
            }
        }
    }


    //只是为了打印好看
    public static void pringLevelAndOrientation(int level, boolean lr) {
        System.out.print("Level " + level + " from ");
        System.out.print(lr ? "left to right: " : "right to left: ");
    }


}



/**
 * @描述：按层遍历二叉树
 * @思路：进行宽度优先遍历，使用队列queue存储当前层和下一层的节点信息； 即： 从queue的头部弹出节点node；若node有孩子，以“先左后右”的形式从尾部进入queue.
 * @复杂度：时间O(N) 空间O(1)
 * @链接：https://www.nowcoder.com/practice/6a1815a85bfc411d9295bc017e6b6dbe
 */
class PrintByLevel {


    /*
     * 宽度优先遍历进阶版 - 按层换行打印
     * 如何确定换行？
     * 记录下"当前行的最右节点last" 和 "下一行的最右节点nlast"
     * 换行时刻：当前节点==last,然后更新last: last = nlast
     *
     * 结果形式：
     * Level 1：1
     * Level 2：2 3
     * Level 3：4 5
     */
    public static void printByLevel2(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        int level = 1;
        TreeNode last = root; //当前行的最右节点
        TreeNode nlast = null; //下一行的最右节点

        queue.offer(root);
        System.out.print("Level " + level++ + " : ");
        while (!queue.isEmpty()) {
            TreeNode curr = queue.poll(); // -- 核心点
            System.out.print(curr.value + " ");

            if (curr.left != null) {
                queue.offer(curr.left);
                nlast = curr.left;
            }
            if (curr.right != null) {
                queue.offer(curr.right);
                nlast = curr.right;
            }

            //换行时刻(注：其中!queue.isEmpty()判断只是为了打印好看,可忽略)
            if (curr == last && !queue.isEmpty()) {
                last = nlast;
                System.out.print("\nLevel " + level++ + " : ");
            }
        }
    }


    /*
     * 宽度优先遍历进阶版 - 按层换行打印
     * 如何确定换行？
     * 标识出 当前层和下一层的分界位置
     * 将队列中的值按层一次一次遍历；即：一次性将当前队列中的当前层的元素遍历完，再在一次性遍历下一层队列元素； 重点在于标识当前层和下一层的分界位置；
     */
    public static void printByLevel3(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        int level = 1;

        queue.offer(root);
        System.out.print("Level " + level++ + ":");
        while (!queue.isEmpty()) {
            int length = queue.size();  // - 核心点  区分：标识当前层和下一层的分界位置
            //换行时刻
            for (int i = 0; i < length; i++) {
                TreeNode curr = queue.poll();
                if (curr.left != null) {
                    queue.offer(curr.left);
                }
                if (curr.right != null) {
                    queue.offer(curr.right);
                }
                System.out.print(curr.value + " ");
            }

            //注：其中!queue.isEmpty()判断可忽略，这里只是为了打印好看，才加的判断
            if (!queue.isEmpty()) {
                System.out.print("\nLevel " + level++ + " : ");
            }

        }
    }



}



class TreeUtils {

    /**
     * 通过控制台输入的方式，采用递归的方式创建一颗二叉树
     */
    public static TreeNode<String> makeBinaryTreeByInput(BufferedReader in) throws Exception {
        String[] nodeVals = in.readLine().split(" ");
        //数组中第一个数是根节点
        TreeNode<String> node = new TreeNode<>(nodeVals[0]);
        //通过递归确定了层数
        if (!"0".equals(nodeVals[1])) {
            node.left = makeBinaryTreeByInput(in);
        }
        if (!"0".equals(nodeVals[2])) {
            node.right = makeBinaryTreeByInput(in);
        }
        return node;
    }

}



class TreeNode<T> {
    public T value;
    public TreeNode<T> left;
    public TreeNode<T> right;

    public TreeNode(T value) {
        this.value = value;
    }

    public TreeNode() {
    }

    public TreeNode(TreeNode left, T value, TreeNode right) {
        this.left = left;
        this.value = value;
        this.right = right;
    }


    public static int getHeight(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int i = getHeight(root.left);
        int j = getHeight(root.right);
        return (i < j) ? j + 1 : i + 1;
    }


    public static int getSize(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return 1 + getSize(root.left) + getSize(root.right);
    }

}