[剑指offer学习心得]之:从上往下打印二叉树

时间:2022-05-19 16:25:24

题目:从上往下打印出二叉树的每个结点,同一层的结点按照从左向右的顺序打印。

解题思路

其实一想就觉得是宽度优先遍历。当然这样想是不是太粗暴了,循序渐进循序渐进

这道题实质就是考察树的遍历算法,只是这种算法不是我们熟知的那三种,所以呢我们可能一下子也想不清楚遍历的过程,所以可以先好好分析一下下面这棵树:

8
| \
6 10
| \ | \
5 7 9 11

按照层次打印顺序决定应该先打印根结点,所以可以从树的根结点开始分析啦。为了接下来能够打印值为8的左右两个子结点,我们应该在遍历到该结点时把值为6和10的两个结点保存到一个容器里,现在容器内就有两个结点了。按照从左到右的打印要求,所以先取出值为6的结点。打印出值6之后把它的值分别为5和7的两个结点放入数据容器中。此时容器中有三个结点:10、5、7。接下来我们从数据容器中取出值为10的结点。10是比5、7结点先放入的,因此不难看出这个数据容器应该是一个队列。由于值为5、7、9、11的结点都没有子结点,因此只要依次打印即可。

所以我们可以找出这样一条规律:每一次打印一个结点的时候,如果该结点有子结点,则把该结点的子结点放到一个队列的末尾。接下来到队列的头部取出最早进入队列的结点,重复前面的打印操作,直到队列中所有的结点都被打印出来为止。

import java.util.LinkedList;
import java.util.Queue;

public class PrintFromTopToBottom {

/**
* 二叉树节点类
*/

public static class BinaryTreeNode {
int value;
BinaryTreeNode left;
BinaryTreeNode right;
}

public static void printFromTopToBottom(BinaryTreeNode root){
if(root==null){
return;
}

Queue<BinaryTreeNode> list=new LinkedList<BinaryTreeNode>();
list.add(root);
BinaryTreeNode curNode;
while(!list.isEmpty()){
curNode=list.remove();
System.out.print(curNode.value+" ");
if(curNode.left!=null){
list.add(curNode.left);
}
if(curNode.right!=null){
list.add(curNode.right);
}
}
}

public static void main(String[] args){
// 8
// / \
// 6 10
// / \ / \
// 5 7 9 11
BinaryTreeNode root = new BinaryTreeNode();
root.value = 8;
root.left = new BinaryTreeNode();
root.left.value = 6;
root.left.left = new BinaryTreeNode();
root.left.left.value = 5;
root.left.right = new BinaryTreeNode();
root.left.right.value = 7;
root.right = new BinaryTreeNode();
root.right.value = 10;
root.right.left = new BinaryTreeNode();
root.right.left.value = 9;
root.right.right = new BinaryTreeNode();
root.right.right.value = 11;
printFromTopToBottom(root);
// 1
// /
// 3
// /
// 5
// /
// 7
// /
// 9
BinaryTreeNode root2 = new BinaryTreeNode();
root2.value = 1;
root2.left = new BinaryTreeNode();
root2.left.value = 3;
root2.left.left = new BinaryTreeNode();
root2.left.left.value = 5;
root2.left.left.left = new BinaryTreeNode();
root2.left.left.left.value = 7;
root2.left.left.left.left = new BinaryTreeNode();
root2.left.left.left.left.value = 9;
System.out.println("\n");
printFromTopToBottom(root2);
// 0
// \
// 2
// \
// 4
// \
// 6
// \
// 8
BinaryTreeNode root3 = new BinaryTreeNode();
root3.value = 0;
root3.right = new BinaryTreeNode();
root3.right.value = 2;
root3.right.right = new BinaryTreeNode();
root3.right.right.value = 4;
root3.right.right.right = new BinaryTreeNode();
root3.right.right.right.value = 6;
root3.right.right.right.right = new BinaryTreeNode();
root3.right.right.right.right.value = 8;
System.out.println("\n");
printFromTopToBottom(root3);
// 1
BinaryTreeNode root4 = new BinaryTreeNode();
root4.value = 1;
System.out.println("\n");
printFromTopToBottom(root4);
// null
System.out.println("\n");
printFromTopToBottom(null);
}
}