在昨天的推文中, 我们给大家讲了利用图表来构建自己的程序思路, 在最后还给大家留下了一道拓展题, 我们来看看大家有没有从中得到提升.
面试题: 从上到下打印二叉树的每个结点, 同一层按照从左到右的顺序打印. 例如数的结构如下:
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 个结点的复杂链表.
image.png
来源: http://www.jianshu.com/p/843ca3a41aa4