Back to Trees
Medium
Binary Tree Level Order Traversal
Given the `root` of a binary tree, return the level order traversal of its nodes' values. (i.e., from left to right, level by level).
Examples
Input:root = [3,9,20,null,null,15,7]
Output:[[3],[9,20],[15,7]]
Input:root = [1]
Output:[[1]]
Constraints
The number of nodes in the tree is in the range [0, 2000].-1000 <= Node.val <= 1000
Approach
Use Breadth-First Search (BFS) with a queue. Start by pushing the root into the queue. While the queue is not empty, get the number of nodes at the current level (`queue.size()`). Iterate that many times to process all nodes on the current level. For each node, add its value to a sub-list, and push its non-null children into the queue. Add the sub-list to the final result after the level iteration is done.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(n)
The space complexity is determined by the maximum number of nodes at any level, which is at most n/2.
Solution.java
class Solution { public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) return res; Queue<TreeNode> q = new LinkedList<>(); q.offer(root); while (!q.isEmpty()) { int levelSize = q.size(); List<Integer> currentLevel = new ArrayList<>(); for (int i = 0; i < levelSize; i++) { TreeNode node = q.poll(); currentLevel.add(node.val); if (node.left != null) q.offer(node.left); if (node.right != null) q.offer(node.right); } res.add(currentLevel); } return res; }}