题目
从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
分析
如下图示，
输出的结果应该是：
8
6 10
5 7 9 11
这个和层序遍历不一样的就是，我们需要记录这个数到底来自哪一行。
我们可以使用两个队列。第一个队列记录当前正在被遍历的这一行的节点，遍历一个节点时，将他的左右孩子（也就是下一层）存在第二个队列中，因为队列是先进先出， 所以我们就按照从左到右的顺序依次遍历就行。
第二种，也就是我采用的是，只使用一个队列（其实也可以使用栈，只要注意顺序就好）。每次遍历完一层，就在这一层的最后加一个null。作为层的结束符。
代码
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer> > resultList = new ArrayList<>();
if (pRoot == null) {
return resultList;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.add(pRoot);
queue.add(null);
while (queue.peek() != null) {
ArrayList<Integer> currentList = new ArrayList<>();
TreeNode tempNode = queue.peek();
while (tempNode != null) {
currentList.add(tempNode.val);
// 从左到右一次加入队列
if (tempNode.left != null) {
queue.add(tempNode.left);
}
if (tempNode.right != null) {
queue.add(tempNode.right);
}
queue.remove();
tempNode = queue.peek();
}
queue.remove();
queue.add(null);
resultList.add(currentList);
}
return resultList;
}
}
补充
Queue接口与List、Set同一级别，都是继承了Collection接口。LinkedList实现了Queue接 口。Queue接口窄化了对LinkedList的方法的访问权限 （即在方法中的参数类型如果是Queue时，就完全只能访问Queue接口所定义的方法 了，而不能直接访问 LinkedList的非Queue的方法），以使得只有 恰当的方法才可以使用。BlockingQueue 继承了Queue接口。
队列是一种数据结构．它有两个基本操作：在队列尾部加人一个元素，和从队列头部移除一个元素就是说，队列以一种先进先出的方式管理数据，如果你试图向一个 已经满了的阻塞队列中添加一个元素或者是从一个空的阻塞队列中移除一个元索，将导致线程阻塞．在多线程进行合作时，阻塞队列是很有用的工具。工作者线程可 以定期地把中间结果存到阻塞队列中而其他工作者线线程把中间结果取出并在将来修改它们。队列会自动平衡负载。如果第一个线程集运行得比第二个慢，则第二个 线程集在等待结果时就会阻塞。如果第一个线程集运行得快，那么它将等待第二个线程集赶上来。下表显示了jdk1.5中的阻塞队列的操作：
add 增加一个元索 如果队列已满，则抛出一个IIIegaISlabEepeplian异常
remove 移除并返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
element 返回队列头部的元素 如果队列为空，则抛出一个NoSuchElementException异常
offer 添加一个元素并返回true 如果队列已满，则返回false
poll 移除并返问队列头部的元素 如果队列为空，则返回null
peek 返回队列头部的元素 如果队列为空，则返回null
put 添加一个元素 如果队列满，则阻塞
take 移除并返回队列头部的元素 如果队列为空，则阻塞
remove、element、offer 、poll、peek 其实是属于Queue接口。
