题目描述:
从上往下打印出二叉树的每个节点,同层节点从左至右打印。
解决思路:
二叉树见下图,我们要打印的顺序是:1,2,3,4,5,6,7,8,9,10;可以看到我们先要打印根节点,之后打印第二层从左到右。我们这边要用到队列容器,先进先出的特点。首先我们在队列中插入根结点。
1、然后我们取出队列中的节点,并且打印,同时将该节点的左右节点(不为空的节点,空节点不用插入)依次压入队列中,则此时队列中有:2,3两个节点。
2.、然后继续步骤1.取出节点2,并插入2的左右子节点(4,5),此时队列:3,4,5;
3、然后继续步骤1.取出节点3,并插入2的左右子节点(6,7),此时队列:4,5,6,7;以此循环直至队列为空才停止;
java源代码
import java.util.*;
class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
public class Solution {
private ArrayList<Integer> list=new ArrayList<Integer>();
private Queue<TreeNode> queue=new LinkedList<TreeNode>();
public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
if(root!=null){
queue.offer(root);
}
while(queue.peek()!=null){
removeNext();
}
return list;
}
/*
*每次在队列中取出一个节点,并将其值插入到List中,
*此外每次取出一个节点需要把这个节点的子节点插入队列
*/
public void removeNext(){
TreeNode temp=queue.poll();
if(temp!=null){
list.add(temp.val);
if(temp.left!=null){
queue.offer(temp.left);
}
if(temp.right!=null){
queue.offer(temp.right);
}
}
else
return;
}
}