从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
例如:
给定二叉树: [3,9,20,null,null,15,7],
3
/
9 20
/
15 7
返回：
[3,9,20,15,7]
层序遍历的时候考虑用队列来存放每一层的节点信息。
- 先将根节点root进栈
- 然后取栈头元素，将其不为null的子节点放入栈中，将栈头元素出栈。
- 当栈为空的时候遍历结束
下面距离说明：
初始状态：
先将根节点放入栈中：
取出队头元素，其子节点值均不为0，则先左后右分别入队。
然后取出队头的节点：9，发现其左右子节点均为null，则其子节点不入队，直接将该节点出队。
然后取出队头的节点：20，其左右基点均不为null，则先左后右入队。
然后取出队头元素：15，发现其左右节点皆为null，直接将该节点出栈。
同样，取出队头元素：7，发现其左右节点皆为null，直接将该节点出栈。
然后看到此时栈为空，遍历过程结束。
看代码：
class Solution {
public int[] levelOrder(TreeNode root) {
List res = new ArrayList();
Queue que = new linkedList();
//要预先判断root是否为null，否则root==null时会抛出空指针异常
if(root == null){return new int[0];}
que.offer(root);
while(!que.isEmpty()){
TreeNode now = que.poll();
res.add(now.val);
if(now.left != null){
que.offer(now.left);
}
if(now.right != null){
que.offer(now.right);
}
}
int[] result = new int[res.size()];
for(int i = 0;i < res.size();i++){
result[i] = res.get(i);
}
return result;
}
}
要点总结：
-
考虑到普适性，一定要考虑到边界情况，当root==null时如果不用if语句做判断，由于null没有左右节点，后面在取now.left和now.right时会抛出空指针异常。
-
要注意常用api的积累：
Queue:
remove：移除并返回队头的一个元素，如果队列为空则抛出异常
add：向队尾插入一个元素，如果队列已满则抛出一个异常
element：返回队头的一个元素，如果队列为空则抛出异常
poll：移除并返回队头的一个元素，如果队列为空则返回null
peek：返回队头的一个元素，如果队列为空则返回null
offer：向队尾插入一个元素并返回true，如果队列已满则返回false
ArrayList
添加元素：add（val）
给指定位置添加元素：add（index，val）
按索引取值：get( i )
按索引删除元素并返回值：remove（index）
按对象删除元素：remove（obj）
获取数组大小：size（）
清空数组中元素：clear（）
