【剑指offer】面试题32:从上到下打印二叉树
题目1:不分行从上到下打印二叉树。从上往下打印出二叉树的每个节点,同一层的节点从左到右的顺序打印。
牛客网链接:https://www.nowcoder.com/questionTerminal/7fe2212963db4790b57431d9ed259701
例如输入下图的二叉树,则依次打印出:8,6,10,5,7,9,11。
这道题实质上考察的就是树的遍历算法,只是这种遍历不是我们熟悉的前序、中序或者后序遍历。由于我们不太熟悉这种按层遍历的方法,可能一下子也想不清楚遍历的过程。
因为按层打印的顺序决定应该先打印的根节点,所以我们从树的根节点开始分析。为了接下来能够打印8的结点的两个子节点,我们应该在遍历到该结点时把值为6和10的两个结点保存到一个容器中,现在容器内就有两个结点了。按照从左到右打印的要求,我们先取出值为6的结点。打印出6后把它的值分别为5和7的两个结点放入数据容器。此时数据容器中有3个结点,值分别为10,5,7。接下来我们从数据容器中取出值为10的结点。注意到值为10的结点比值为5、7的结点先放入容器,此时又比这两个结点先取出,这就是我们通常说的**先入先出**,因此不难看出这个容器应该是一个**队列**。由于值为5,7,9,11的结点都没有子节点,因此只要依次打印即可。
通过分析具体例子,我们可以找到从上到下打印二叉树的规律:每次打印一个结点的时候,如果该节点有子节点,把该节点的子节点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的节点,重复前面打印操作,直到队列中所有的节点都被打印出来。
代码实现:
package com.zju.offer.tree;
import java.util.ArrayList;
/**
* 不分行从上到下打印二叉树
* 从上往下打印出二叉树的每个节点,同一层的节点从左到右的顺序打印
*/
public class PrintFromTopToBottom {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public ArrayList<Integer> printFromTopToBottom(TreeNode root){
ArrayList<Integer> list = new ArrayList<>();
// 模拟一个队列,也可以用LinkedList
ArrayList<TreeNode> queue = new ArrayList<>();
if(root == null){
return list;
}
queue.add(root);
while(queue.size() != 0){
// 将queue中第一个元素移除
TreeNode temp = queue.remove(0);
// 如果将要移除的节点有左子节点,则加入queue
if(temp.left != null){
queue.add(temp.left);
}
// 如果将要移除的节点有右子节点,则加入queue
if(temp.right != null){
queue.add(temp.right);
}
// 将temp的值加入list中
list.add(temp.val);
}
return list;
}
}
本题实现代码中用的是一个ArrayList集合去模拟的队列,每次移除下标为0的元素即为队列的头元素,也符合队列“先进先出的特点”。
本题扩展:如何广度优先遍历一幅有向图?同样也可以基于队列实现。树是图的一种特殊退化形式,从上到下按层遍历二叉树,从本质上来说就是广度优先遍历二叉树。
举一反三:不管是广度优先遍历一幅有向图还是一棵树,都要用到队列。首先把起始节点(对树而言是根节点)放入队列。接下来每次从队列的头部取出一个节点,遍历这个节点之后把它能到达的节点(对树而言是子节点)都依次放入到队列。重复这个遍历过程,直到队列中的节点全部被遍历为止。
题目2:分行从上到下打印二叉树。从上到下按层打印二叉树,同一层的节点按从左到右的顺序打印,每一层打印到一行。
如下案例所示:
打印结果为:
8
6 10
5 7 9 11
这道题和前面的题类似,也可以用一个队列来保存将要打印的节点。为了把二叉树的每一行单独打印到一行里,我们需要两个变量:一个变量表示在当前层中还没有打印的节点数;另外一个变量表示下一层节点的数目。
public class PrintFromTopToBottom {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public ArrayList<Integer> printFromTopToBottom_Method1(TreeNode root){
ArrayList<Integer> list = new ArrayList<>();
// 模拟一个队列,也可以用LinkedList
ArrayList<TreeNode> queue = new ArrayList<>();
if(root == null){
return list;
}
queue.add(root);
int nextLevel = 0;
int toBePrinted = 1;
while(queue.size() != 0){
// 将queue中第一个元素移除
TreeNode temp = queue.remove(0);
// 如果将要移除的节点有左子节点,则加入queue
if(temp.left != null){
queue.add(temp.left);
nextLevel++;
}
// 如果将要移除的节点有右子节点,则加入queue
if(temp.right != null){
queue.add(temp.right);
nextLevel++;
}
// 将temp的值加入list中
list.add(temp.val);
System.out.print(temp.val + " ");
--toBePrinted;
if(toBePrinted == 0){
System.out.println();
toBePrinted = nextLevel;
nextLevel = 0;
}
}
return list;
}
// 测试
public static void main(String[] args) {
PrintFromTopToBottom p = new PrintFromTopToBottom();
TreeNode root = p.new TreeNode(8);
TreeNode node1 = p.new TreeNode(6);
TreeNode node2 = p.new TreeNode(10);
TreeNode node3 = p.new TreeNode(5);
TreeNode node4 = p.new TreeNode(7);
TreeNode node5 = p.new TreeNode(9);
TreeNode node6 = p.new TreeNode(11);
root.left = node1;
root.right = node2;
node1.left = node3;
node1.right = node4;
node2.left = node5;
node2.right = node6;
p.printFromTopToBottom_Method1(root);
}
}
变量 toBePrinted 表示在当前层中还没有打印的节点数,而变量 nextLevel 表示下一层的节点数。如果一个节点有子节点,则每把一个子节点加入队列,同时把变量 nextLevel 加1。每打印一个节点,toBePrinted 减 1。当 toBePrinted 变成 0 时,表示当前层的所有节点已经打印完毕,可以继续打印下一层。
题目3:之字形打印二叉树。
请实现一个函数按照之字形打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右至左的顺序打印,第三行按照从左到右的顺序打印,其他行以此类推。
按之字形顺序打印二叉树需要两个栈。我们在打印某一层的节点时,把下一层的子节点保存到相应的栈里。如果当前打印的是奇数层(第一层、第三层等),则先保存左子节点再保存右子节点到第一个栈里(因为栈的后进先出特点);如果当前打印的是偶数层(第二层、第四层等),则先保存右子节点再保存左子节点到第二个栈里。接下来逐个把位于栈顶的节点弹出栈并打印即可。
使用嵌套集合类型来保存 stack1 和 stack2 中弹出的数据,每一个内层小集合中保存一层的数据。
package com.zju.offer.tree;
import java.util.ArrayList;
import java.util.Stack;
public class PrintFromTopToBottom {
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
/**
* 之字形打印:奇数从左往右打印、偶数从右往左打印
*/
public ArrayList<ArrayList<Integer>> Print(TreeNode root){
// 层数索引
int layer = 1;
// stack1 保存奇数层节点
Stack<TreeNode> stack1 = new Stack<TreeNode>();
stack1.push(root); // 因为根节点是奇数层,所以将根节点先保存到stack1中
// stack2 保存偶数层节点
Stack<TreeNode> stack2 = new Stack<TreeNode>();
// 采用双层集合,每一个内层集合存储一层数据
ArrayList<ArrayList<Integer>> list = new ArrayList<ArrayList<Integer>>();
while(!stack1.empty() || !stack2.empty()){
if(layer % 2 != 0){
// 打印奇数层
ArrayList<Integer> temp = new ArrayList<Integer>();
while(!stack1.empty()){
TreeNode node = stack1.pop();
if(node != null){
temp.add(node.val);
System.out.print(node.val + " ");
// 由于当前层是奇数层,所以它的下一层是要从右往左打印
// 因此按照栈的"后进先出"的特性,先保存左子节点,再保存右子节点
stack2.push(node.left);
stack2.push(node.right);
}
}
if(!temp.isEmpty()){
list.add(temp);
layer++;
System.out.println();
}
}else{
// 打印偶数层
ArrayList<Integer> temp = new ArrayList<Integer>();
while(!stack2.isEmpty()){
TreeNode node = stack2.pop();
if(node != null){
temp.add(node.val);
System.out.print(node.val + " ");
// 由于当前层是偶数层,所以它的下一层是要从左往右打印
// 因此按照栈的"后进先出"的特性,先保存右子节点,再保存左子节点
stack1.push(node.right);
stack1.push(node.left);
}
}
if(!temp.isEmpty()){
list.add(temp);
layer++;
System.out.println();
}
}
}
return list;
}
// 测试
public static void main(String[] args) {
PrintFromTopToBottom p = new PrintFromTopToBottom();
TreeNode root = p.new TreeNode(8);
TreeNode node1 = p.new TreeNode(6);
TreeNode node2 = p.new TreeNode(10);
TreeNode node3 = p.new TreeNode(5);
TreeNode node4 = p.new TreeNode(7);
TreeNode node5 = p.new TreeNode(9);
TreeNode node6 = p.new TreeNode(11);
root.left = node1;
root.right = node2;
node1.left = node3;
node1.right = node4;
node2.left = node5;
node2.right = node6;
p.Print(root);
}
}
还没有评论,来说两句吧...