面试 17：从上到下打印二叉树
在昨天的推文中，我们给大家讲了利用图表来构建自己的程序思路，在最后还给大家留下了一道拓展题，我们来看看大家有没有从中得到提升。
面试题：从上到下打印二叉树的每个结点，同一层按照从左到右的顺序打印。例如数的结构如下：
1
2 3
4 5 6 7则依次打印 1、2、3、4、5、6、7
提前思考测试用例
依然是我们的第一步，提前想好我们的测试用例。
传入一个空树，什么也不打印；
传入题干上的树，打印正确结果；
传入部分有子结点，部分没有子结点的非完全二叉树，打印正确结果。
提炼程序逻辑
这是一道二叉树的遍历问题，不同点在于它和我们平常所学习的前序遍历、中序遍历和后序遍历，看起来比较简单，但却很难抽象。
如题，我们希望打印的顺序是先打印根结点，然后再依次打印左结点和右结点，再继续打印左结点的左右结点，依次类推……
我们知道，要打印一个结点的左右结点，根据二叉树的定义可得知，我们必须得先知道这个结点，所以我们一定得找到一个容器去装下它。
快速过一遍我们的容器类，我们比较容易知道队列可以极好地达到我们的要求，因为它的先进先出和我们这个需求非常吻合。
但比较遗憾的是，即使想到了这一点，有的小伙伴也容易犯迷糊，所以我们不得不用昨天所学习到的图表法进行思路地整理。
| 步骤 | 操作 | 队列 |
|---|---|---|
| 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方法在错误的时候会报异常，两者各有优劣。
验证测试用例
代码写毕，开始验证我们的测试用例。
传入异常值，直接返回，测试通过；
传入单个结点，测试通过；
传入非完全二叉树，测试通过；
传入完全二叉树，测试通过。
课后习题
依然还是要放上下一次推文的习题讲解，下一题来自《剑指 Offer》 的面试题 26：复杂链表的复制
请实现复杂链表的复制，在复杂链表中，每个结点除了 next 指针指向下一个结点外，还有一个 sibling 指向链表中的任意结点或者 NULL。比如下图就是一个含有 5 个结点的复杂链表。
—————END—————
我是南尘，只做比心的公众号，欢迎关注我。
推荐阅读：
欢迎关注南尘的公众号：nanchen
做不完的开源，写不完的矫情，只做比心的公众号，如果你喜欢，你可以选择分享给大家。如果你有好的文章，欢迎投稿，让我们一起来分享。