Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).
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,一个保存当前这行所有的Node, 然后另一个数组保存下一行所有的nodes.
/**
* Definition of TreeNode:
* public class TreeNode {
* public int val;
* public TreeNode left, right;
* public TreeNode(int val) {
* this.val = val;
* this.left = this.right = null;
* }
* }
*/ 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>> allLists = new ArrayList<>();
if (root == null) return allLists; ArrayList<Integer> nums = new ArrayList<>();
ArrayList<TreeNode> list1 = new ArrayList<>();
ArrayList<TreeNode> list2 = new ArrayList<>(); list1.add(root); while(list1.size() != ) {
for (TreeNode node : list1) {
nums.add(node.val);
if (node.left != null) list2.add(node.left);
if (node.right != null) list2.add(node.right);
}
list1.clear();
allLists.add(new ArrayList<Integer>(nums));
nums.clear();
ArrayList<TreeNode> temp = list1;
list1 = list2;
list2 = temp;
}
return allLists;
}
}