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,null,null,15,7],
3
/ \
9 20
/ \
15 7
return its level order traversal as:
[
[3],
[9,20],
[15,7]
]
Explanation - Normally breath first search (BFS) can be done using while loop but in this problem a each list need to be create for each level, so we can use a for loop here and take the current size of Queue and iterate that loop because at this time only one level's nodes are added to Queue.
Like first time size will be 1(3), second time 2(9,20), third time it will be 2(15,7).
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<List<Integer>>();
Queue<TreeNode> q = new LinkedList();
q.add(root);
while(!q.isEmpty()){
List<Integer> ll = new ArrayList();
int n = q.size();
for(int i=0;i<n;i++){
TreeNode temp = q.peek();
q.remove();
if(temp!=null){
ll.add(temp.val);
if(temp.left != null) q.add(temp.left);
if(temp.right != null) q.add(temp.right);
}
}
if(!ll.isEmpty())list.add(ll);
//System.out.println(ll);
}
return list;
}
}