Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
For example:
Given binary tree {3,9,20,#,#,15,7},
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
] 对每一层的节点都用ArrayList<TreeNode> cur保存，每次循环时把cur里每个非空节点值拿出来并保存到ArrayList<Integer> temp中， 并且子节点保存到新的ArrayList<TreeNode>中。最后如果 temp 非空，就加入到结果集中。最后cur 指向新的ArrayList<TreeNode>。
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> re = new ArrayList<List<Integer>>();
List<TreeNode> lst = new ArrayList<TreeNode>();
lst.add(root);
while(lst.size()>0){
List<Integer> temp = new ArrayList<Integer>();
List<TreeNode> childrenlst = new ArrayList<TreeNode>();
for(int i=0;i<lst.size();i++){
TreeNode curNode = lst.get(i);
if(curNode!=null){
temp.add(lst.get(i).val);
childrenlst.add(curNode.left);
childrenlst.add(curNode.right);
}
}
if(temp.size()>0)
re.add(temp);
lst = childrenlst;
}
return re;
}
Level Order Traverse II 就是反一反。