面试 17：从上到下打印二叉树（剑指 Offer 26 题 Ja

在昨天的推文中，我们给大家讲了利用图表来构建自己的程序思路，在最后还给大家留下了一道拓展题，我们来看看大家有没有从中得到提升。

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

​ 1
2 3
4 5 6 7

则依次打印 1、2、3、4、5、6、7

提前思考测试用例

依然是我们的第一步，提前想好我们的测试用例。

1. 传入一个空树，什么也不打印；
2. 传入题干上的树，打印正确结果；
3. 传入部分有子结点，部分没有子结点的非完全二叉树，打印正确结果。

提炼程序逻辑

这是一道二叉树的遍历问题，不同点在于它和我们平常所学习的前序遍历、中序遍历后后序遍历，看起来比较简单，但却很难抽象。

如题，我们希望打印的顺序是先打印根结点，然后再依次打印左结点和右结点，再继续打印左结点的左右结点，依次类推......

我们知道，要打印一个结点的左右结点，根据二叉树的定义可得知，我们必须得先知道这个结点，所以我们一定得找到一个容器去装下它。

快速过一遍我们的容器类，我们比较容易知道队列可以极好地达到我们的要求，因为它的先进先出和我们这个需求非常吻合。

但比较遗憾的是，即使想到了这一点，有的小伙伴也容易犯迷糊，所以我们不得不用昨天所学习到的图表法进行思路地整理。

步骤	操作	队列
1	打印结点 1，入队左右结点	2、3
2	打印结点 2，入队左右结点	3、4、5
3	打印结点 3，入队左右结点	4、5、6、7
4	打印结点 4，无子结点无需入队操作	5、6、7
5	打印结点 5，无子结点无需入队操作	6、7
6	打印结点 6，无子结点无需入队操作	7
7	打印结点 7，无子结点无需入队操作

编写代码

有了上面的思路，我们便可以开始编写代码了。

public class Test17 {

    private static class TreeNode {
        int data;
        TreeNode left;
        TreeNode right;

        TreeNode(int data) {
            this.data = data;
        }
    }

    private static void printOrder(TreeNode root) {
        if (root == null)
            return;
        Queue<TreeNode> queue = new LinkedList<>();
        // 先添加根结点
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node != null) {
                System.out.print(node.data + ",");
                if (node.left != null)
                    queue.offer(node.left);
                if (node.right != null)
                    queue.offer(node.right);
            }
        }
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.right = new TreeNode(3);
        root.left.left = new TreeNode(4);
        root.left.right = new TreeNode(5);
        root.right.left = new TreeNode(6);
        root.right.right = new TreeNode(7);
        printOrder(root);
        System.out.println();
        printOrder(null);
        root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.left.right.left = new TreeNode(5);
        System.out.println();
        printOrder(root);
    }
}

代码实现确实比较简单，唯一让大家疑惑的是我的出队列用的是 poll 而不是其他资料中用的 remove，进队列用的是 offer 而不是 add。

offer 和 poll 方法相对于 add 和 remove 方法更安全，它们是通过返回值来判断是否入队和出队成功的，而 add 和 remove 方法在错误的时候会报异常，两者各有优劣。

验证测试用例

代码写毕，开始验证我们的测试用例。

1. 传入异常值，直接返回，测试通过；
2. 传入单个结点，测试通过；
3. 传入非完全二叉树，测试通过；
4. 传入完全二叉树，测试通过。

课后习题

依然还是要放上下一次推文的习题讲解，下一题来自《剑指 Offer》 的面试题 26：复杂链表的复制

请实现复杂链表的复制，在复杂链表中，每个结点除了 next 指针指向下一个结点外，还有一个 sibling 指向链表中的任意结点或者 NULL。比如下图就是一个含有 5 个结点的复杂链表。

image.png