5
/ \
3 10
/ \ / \
1 4 7 8
Level order traversal
[ [5], [3, 10], [1, 4, 7, 8]]
Level order traversal is similar to breadth first search. The problem can be solved using a queue. Start traversing from the root, push to queue. Pop the element from the queue print it and push its children in queue. Continue till the queue is empty
public List<List<Integer>> levelOrder(TreeNode root) {
if (root == null)
return Collections.EMPTY_LIST;
Queue<TreeNode> queue = new LinkedList();
queue.add(root);
int count =1;
List<List<Integer>> finalList = new ArrayList();
while(count != 0) {
List<Integer> list = new ArrayList();
Queue<TreeNode> nextQueue = new LinkedList();
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
list.add(node.val);
count--;
if (node.left != null) {
nextQueue.add(node.left);
}
if (node.right != null) {
nextQueue.add(node.right);
}
}
finalList.add(list);
count = nextQueue.size();
queue = nextQueue;
}
return finalList;
}