题目:从上到下打印二叉树
- 不分行从上到下打印二叉树
- 分行从上到下打印二叉树
- 之字形打印二叉树
题目 1. 不分行从上到下打印二叉树
从上到下打印出二叉树的每个节点,同一层的节点按照从左到右的顺序打印。
二叉树结点
1 | public static class BinaryTreeNode { |
举例说明
如下的二叉树
1 | 8 |
则依次打印出8 6 10 5 7 9 11
解题思路
考查树的遍历算法。
从上到下打印二叉树的规律:
- 每一次打印一个结点的时候,如果该结点有子结点, 则把该结点的
子结点放到一个队列的末尾
- 接下来到队列的
头部取出
最早进入队列的结点 - 重复前面的打印操作,直至队列中
所有的结点都被打印出来为止
代码实现:
1 | import java.util.Queue; |
扩展:
- 从上到下按层遍历二叉树,从本质上来说就是
广度优先遍历二叉树
- 不管是广度优先遍历一幅有向图还是一棵树,都要用到
队列
- 首先把
起始节点(树中为根结点)
放入队列,接下来每次从队列的头部取出一个节点,遍历这个节点后把它能到达的节点(树中为子结点)
都依次放入队列。重复这个遍历过程,直到队列中的节点全部都遍历为止
题目 2. 分行从上到下打印二叉树
从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。
举例说明
如下的二叉树
1 | 8 |
则依次打印出1
2
38
6 10
5 7 9 11
解题思路
用队列
来保存要打印的节点。
同时我们需要两个变量:一个变量表示在当前层中还没有打印的节点数
;另一个变量表示下一层节点的数目
代码实现
1 | import java.util.LinkedList; |
题目 3. 之字形打印二叉树
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。(每一层打印到一行。)
举例说明
如下的二叉树
1 | 8 |
则依次打印出1
2
38
10 6
5 7 9 11
解题思路
按之字形顺序打印二叉树需要两个栈。
- 我们在打印某一行结点时,把下一层的子结点保存到相应的栈里
- 如果当前打印的是奇数层,则先保存左子结点再保存右子结点到一个栈里
- 如果当前打印的是偶数层,则先保存右子结点再保存左子结点到第二个栈里
代码实现
1 | import java.util.LinkedList; |