Problems
Binary Tree Level Order Traversal
Easy·Tagstreebfsqueue
Problem Statement
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).
Note: Assume a standard `TreeNode` class is already provided in the execution environment, containing `val`, `left`, and `right` properties.
Examples
Example 1
Input
root: [3, 9, 20, null, null, 15, 7]Tree
Output
"[[3], [9, 20], [15, 7]]"Why
Level 0: [3]
Level 1: [9, 20]
Level 2: [15, 7]
Example 2
Input
root: [1]Tree
Output
"[[1]]"Why
The tree only has one node.
Example 3
Input
root: []Output
"[]"Why
An empty tree returns an empty array.
Constraints
- •The number of nodes in the tree is in the range [0, 2000].
- •-1000 <= Node.val <= 1000
Hints
Stuck? Reveal a nudge toward the right pattern, one step at a time.
Hint 1
A standard Breadth-First Search (BFS) explores nodes exactly in the order they were discovered. Which data structure naturally processes items in a First-In-First-Out (FIFO) order?
Hint 2
Use a Queue. Enqueue the root node first. Then, enter a while loop that continues as long as the queue is not empty.
Hint 3
How do you separate the nodes into distinct lists for each level? Before you start popping nodes, check the current `size` of the queue! That size represents exactly how many nodes are on the current level.
Hint 4
Run a `for` loop `size` times to pop the current level's nodes, add their values to a temporary list, and enqueue their non-null children. Once the `for` loop finishes, the level is done, and the queue only contains the next level!