Problem
Given the root of a binary tree, return the level order traversal of its nodes' values.Each level of the tree should be returned as a separate list, starting from the root and continuing level by level.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
root = [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
Output
[[3],[9,20],[15,7]] Solution
This solution uses Breadth-First Search (BFS) with a Queue to process the tree level by level.For each level, the current queue size represents the number of nodes at that level. We process exactly that many nodes and store their values in a separate list.
The children of each node are then added to the queue, allowing the next level to be processed in the following iteration.
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> result = new ArrayList<>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
List<Integer> level = new ArrayList<>();
// Process all nodes at the current level.
for (int i = 0; i < size; i++) {
TreeNode node = queue.poll();
level.add(node.val);
if (node.left != null) {
queue.offer(node.left);
}
if (node.right != null) {
queue.offer(node.right);
}
}
result.add(level);
}
return result;
}
Complexity
Each node is added to and removed from the queue exactly once, resulting in a time complexity ofO(n).
In the worst case, the queue may contain all nodes at the widest level of the tree, resulting in an extra space complexity of
O(n).