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).
Examples:
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]
Example 2:
Input: root = [1]
Output: [[1]]
Explanation:Example 3:
Input: root = []
Output: []
Constraints:
- The number of nodes in the tree is in the range
[0, 100]. -100 <= Node.val <= 100
Approach
- Base Case: If the tree is empty (root == null), return an empty array.
- Initialize Queue: Use a queue to process nodes level by level. Start by pushing the root node.
- Process Each Level:
- For each level, store the number of nodes (levelSize) currently in the queue.
- Process levelSize nodes by:
- Removing each node from the front of the queue.
- Adding its value to the current level array.
- Enqueue its left and right children if they exist.
- Add Level to Result: After processing one level, push the level array to the final result.
- Repeat: Continue until the queue is empty.
- Return Result: Return the array containing node values level by level.
Time Complexity:
Time Complexity = O(n)
Space Complexity:
Space Complexity = O(n)
Dry Run
Input: root = [1, 2, 3, null, 4]
Tree Structure:
1
/ \
2 3
\
4
Initialize:
ans = []
q = [1] (root)
Main loop starts (while q.length):
→ Level 0:
levelArr = []
levelSize = 1
→ i = 0:
curr = 1
q = []
curr.left (2) → q = [2]
curr.right (3) → q = [2, 3]
levelArr.push(1) → levelArr = [1]
→ ans.push([1]) → ans = [[1]]
→ Level 1:
levelArr = []
levelSize = 2
→ i = 0:
curr = 2
q = [3]
curr.left = null
curr.right (4) → q = [3, 4]
levelArr.push(2) → levelArr = [2]
→ i = 1:
curr = 3
q = [4]
curr.left = null
curr.right = null
levelArr.push(3) → levelArr = [2, 3]
→ ans.push([2, 3]) → ans = [[1], [2, 3]]
→ Level 2:
levelArr = []
levelSize = 1
→ i = 0:
curr = 4
q = []
curr.left = null
curr.right = null
levelArr.push(4) → levelArr = [4]
→ ans.push([4]) → ans = [[1], [2, 3], [4]]
Main loop ends (q is empty)
Traversal complete.
Final ans: [[1], [2, 3], [4]]
Output: Result: [[1], [2, 3], [4]]
var levelOrder = function (root) {
if (!root) return [];
let q = [root];
let ans = [];
while (q.length) {
let levelArr = [];
let levelSize = q.length;
for (let i = 0; i < levelSize; i++) {
let curr = q.shift();
curr.left && q.push(curr.left);
curr.right && q.push(curr.right);
levelArr.push(curr.val);
}
ans.push(levelArr);
}
return ans;
};
from collections import deque
def levelOrder(root):
if not root:
return []
q = deque([root])
ans = []
while q:
levelArr = []
levelSize = len(q)
for i in range(levelSize):
curr = q.popleft()
if curr.left:
q.append(curr.left)
if curr.right:
q.append(curr.right)
levelArr.append(curr.val)
ans.append(levelArr)
return ans
class Solution {
public List> levelOrder(TreeNode root) {
if (root == null) return new ArrayList<>();
Queue q = new LinkedList<>();
q.offer(root);
List> ans = new ArrayList<>();
while (!q.isEmpty()) {
List levelArr = new ArrayList<>();
int levelSize = q.size();
for (int i = 0; i < levelSize; i++) {
TreeNode curr = q.poll();
if (curr.left != null) q.offer(curr.left);
if (curr.right != null) q.offer(curr.right);
levelArr.add(curr.val);
}
ans.add(levelArr);
}
return ans;
}
}
#include <iostream>
#include <vector>
#include <queue>
class Solution {
public:
vector> levelOrder(TreeNode* root) {
if (!root) return {};
queue q;
q.push(root);
vector> ans;
while (!q.empty()) {
vector levelArr;
int levelSize = q.size();
for (int i = 0; i < levelSize; i++) {
TreeNode* curr = q.front();
q.pop();
if (curr->left) q.push(curr->left);
if (curr->right) q.push(curr->right);
levelArr.push_back(curr->val);
}
ans.push_back(levelArr);
}
return ans;
}
};
#include <stdio.h>
#include <stdlib.h>
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
if (!root) {
*returnSize = 0;
*returnColumnSizes = NULL;
return NULL;
}
struct TreeNode* q[2000];
int front = 0, rear = 0;
q[rear++] = root;
int** ans = (int**)malloc(2000 * sizeof(int*));
*returnColumnSizes = (int*)malloc(2000 * sizeof(int));
*returnSize = 0;
while (front < rear) {
int levelSize = rear - front;
int* levelArr = (int*)malloc(levelSize * sizeof(int));
for (int i = 0; i < levelSize; i++) {
struct TreeNode* curr = q[front++];
if (curr->left) q[rear++] = curr->left;
if (curr->right) q[rear++] = curr->right;
levelArr[i] = curr->val;
}
ans[*returnSize] = levelArr;
(*returnColumnSizes)[*returnSize] = levelSize;
(*returnSize)++;
}
return ans;
}
public class Solution {
public IList> LevelOrder(TreeNode root) {
if (root == null) return new List>();
Queue q = new Queue();
q.Enqueue(root);
IList> ans = new List>();
while (q.Count > 0) {
List levelArr = new List();
int levelSize = q.Count;
for (int i = 0; i < levelSize; i++) {
TreeNode curr = q.Dequeue();
if (curr.left != null) q.Enqueue(curr.left);
if (curr.right != null) q.Enqueue(curr.right);
levelArr.Add(curr.val);
}
ans.Add(levelArr);
}
return ans;
}
}
