Given a binary tree, return the level order traversal of its nodes‘ values. (ie, from left to right, level by level).
Given binary tree {3,9,20,#,#,15,7},
3
/ 9 20
/ 15 7
return its level order traversal as:
[ [3], [9,20], [15,7] ]
SOLUTION :
这个题有很多解法，包括用两个queue，一个queue＋dummy node 以及只用一个queue的，这里就只说最优解，1 queue的了。
本题借鉴了大神的总结：http://www.1point3acres.com/bbs/thread-139294-1-1.html
基本上几个level order 的二叉树遍历都可以用这套思路。
思路：用queue去模拟层序遍历的过程，就是说要向queue中一层一层的输入，再输出，但是怎么保证输入的是同一层呢，我们用到一个变量，queue.size()，这个很关键，它保证了内层循环（负责向queue输入节点以及从queue拿出节点加入list中）执行次数就是这一层节点的个数。在实现时候的具体思想就是，拿出一个点，就把这个点的左右儿子加入到queue中，从任一一层二叉树来看，就是当这一层的所有点抖拿出来了之后，同时这些点的所有左右儿子也都加进去了。具体实现看代码：
注意事项，queue用LinkedList模拟，queue输入输出分别是add(),remove()。
public class Solution {
/**
* @param root: The root of binary tree.
* @return: Level order a list of lists of integer
*/
public ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
ArrayList<ArrayList<Integer>> result = new ArrayList<ArrayList<Integer>>();
if (root == null){
return result;
}
Queue<TreeNode> queue = new LinkedList<TreeNode>();
queue.add(root);
while (!queue.isEmpty()){
ArrayList<Integer> list = new ArrayList<Integer>();
int size = queue.size();
for (int i = 0; i < size; i++){
TreeNode cur = queue.remove();
if (cur.left != null){
queue.add(cur.left);
}
if (cur.right != null){
queue.add(cur.right);
}
list.add(cur.val);
}
result.add(new ArrayList<Integer>(list));
}
return result;
}
}
[Lintcode] Binary Tree Level Order Traversal
原文：http://www.cnblogs.com/tritritri/p/4858504.html