从上到下打印二叉树

It has been 1124 days since the last update, the content of the article may be outdated.

题目：从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。例如下面的二叉树

依次打印出 8, 6, 10, 5, 7, 9, 11。二叉树节点的定义如下：

private static class BinaryTreeNode {
    private BinaryTreeNode left;
    private BinaryTreeNode right;
    int value;
    public BinaryTreeNode(int value) {
        this.left = null;
        this.right = null;
        this.value = value;
    }
}

这道题考察的是树的层序遍历，对于按层遍历的方法，我们使用队列来辅助遍历，具体方法如下，对于根节点，我们将它放入队列中，然后从队列中取出一个元素进行打印，然后将该节点的左右子节点放入队列中，接着从队列中取出一个元素，打印该元素，然后将该元素的左右子节点添加到队列中，重复上面的过程，直到队列为空，我们从下图来看上面的过程

代码如下

public static void printFromTopToBottom(BinaryTreeNode root) {
    if (root == null) {
        return;
    }
    Queue<BinaryTreeNode> queue = new LinkedList<>();
    // 先将根节点添加进队列
    queue.offer(root);
    // 队列不为空时
    while (!queue.isEmpty()) {
        // 每次将队首元素弹出并打印
        BinaryTreeNode node = queue.poll();
        System.out.println(node.value);
        // 然后将该元素的左右子节点添加进队列
        if (node.left != null) {
            queue.offer(node.left);
        }
        if (node.right != null) {
            queue.offer(node.right);
        }
    }
}

题目：从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。如打印下面二叉树的结果为：

8

6 10

5 7 9 11

这道题目和上面的题目类似，不过我们要用两个变量两保存当前层还要打印的节点数目和下一层要打印的节点数目。我们使用 toBePrinted 来保存当前层还需要打印的节点的数目，nextLevel 来保存下一层要打印的节点数目。当 toBePrinted 不为 0，每添加一个元素时 nextLevel++，每弹出一个元素 toBePrinted--，当 toBePrinted 为 0 时，我们打印换行，并将 nextLevel 赋值给 toBePrinted，并且设置 nextLevel 为 0，代码如下

public static void printWithLevel(BinaryTreeNode root) 
    if (root == null) {
        return;
    }
    Queue<BinaryTreeNode> queue = new LinkedList<>();
    queue.offer(root);
    int nextLevel = 0;
    int toBePrinted = 1;
    while (!queue.isEmpty()) {
        BinaryTreeNode node = queue.poll();
        System.out.print(node.value + "\t");
        toBePrinted--;
        if (node.left != null) {
            queue.offer(node.left);
            nextLevel++;
        }
        if (node.right != null) {
            queue.offer(node.right);
            nextLevel++;
        }
        if (toBePrinted == 0) {
            System.out.println();
            toBePrinted = nextLevel;
            nextLevel = 0;
        }
    }
}

题目：请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三层再按照从左到右的顺序打印，其他行以此类推。

按之字形打印树的过程还是比较复杂的，可能一时难以想到解决方案，可能需要使用具体的例子一步步分析看是否能找到解决方案。以下面的树为例

对于奇数层(从 1 开始)，我们将节点保存到一个栈中，如 stack1，对于偶数层，我们将节点保存到另一个栈中，如 stack2。在奇数层时，我们每次从栈 stack1 中弹出一个元素并打印，并将元素的左孩子(先)和右孩子添加到 stack2 中，当 stack1 为空时，说明该层的元素已全部打印完毕，切换到 stack2，我们每次从 stack2 中弹出一个元素并打印，并将该元素的右孩子(先)和左孩子(后)添加到 stack1 中，当 stack2 为空时，切换到 stack1，直到 stack1 和 stack2 同时为空时，打印过程结束

public static void printZhi(BinaryTreeNode root) {
    if (root == null) {
        return;
    }
    Stack<BinaryTreeNode> stack1 = new Stack<>();
    Stack<BinaryTreeNode> stack2 = new Stack<>();
    stack1.push(root);
    // 表示所在的层数，从 1 开始
    int level = 1;
    while (!stack1.isEmpty() || !stack2.isEmpty()) {
        // 奇数层从stack1中取出元素，并将元素的左孩子和右孩子添加到stack2中
        if (level % 2 == 1) {
            BinaryTreeNode node = stack1.pop();
            System.out.print(node.value + "\t");
            if (node.left != null) {
                stack2.push(node.left);
            }
            if (node.right != null) {
                stack2.push(node.right);
            }
            // 当 stack1 为空，来到下一层
            if (stack1.isEmpty()) {
                System.out.println();
                level++;
            }
        } else {
            // stack2 的过程同上，不过先将右孩子先添加到stack1中
            BinaryTreeNode node = stack2.pop();
            System.out.print(node.value + "\t");
            if (node.right != null) {
                stack1.push(node.right);
            }
            if (node.left != null) {
                stack1.push(node.left);
            }
            if (stack2.isEmpty()) {
                System.out.println();
                level++;
            }
        }
    }
}