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 = [];
let curr = root;
while(curr || stack.length) {
while(curr) {
stack.push(curr);
curr = curr.left;
}
curr = stack.pop();
ans.push(curr.val);
curr = curr.right;
}
return ans;
};
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root):
if not root:
return []
q = deque([root])
ans = []
while q:
levelArr = []
levelSize = len(q)
for _ 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
import java.util.*;
class TreeNode {
int val;
TreeNode left, right;
TreeNode(int x) { val = x; }
}
public class Solution {
public List> levelOrder(TreeNode root) {
List> ans = new ArrayList<>();
if (root == null) return ans;
Queue q = new LinkedList<>();
q.offer(root);
while (!q.isEmpty()) {
int levelSize = q.size();
List levelArr = new ArrayList<>();
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>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
vector> levelOrder(TreeNode* root) {
vector> ans;
if (!root) return ans;
queue q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
vector levelArr;
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>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
typedef struct QueueNode {
TreeNode* node;
struct QueueNode* next;
} QueueNode;
typedef struct {
QueueNode *front, *rear;
} Queue;
Queue* createQueue() {
Queue* q = (Queue*) malloc(sizeof(Queue));
q->front = q->rear = NULL;
return q;
}
void enqueue(Queue* q, TreeNode* node) {
QueueNode* temp = (QueueNode*) malloc(sizeof(QueueNode));
temp->node = node;
temp->next = NULL;
if (!q->rear) {
q->front = q->rear = temp;
return;
}
q->rear->next = temp;
q->rear = temp;
}
TreeNode* dequeue(Queue* q) {
if (!q->front) return NULL;
QueueNode* temp = q->front;
q->front = q->front->next;
if (!q->front) q->rear = NULL;
TreeNode* node = temp->node;
free(temp);
return node;
}
using System.Collections.Generic;
public class TreeNode {
public int val;
public TreeNode left, right;
public TreeNode(int val = 0, TreeNode left = null, TreeNode right = null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public IList> LevelOrder(TreeNode root) {
var ans = new List>();
if (root == null) return ans;
Queue q = new Queue();
q.Enqueue(root);
while (q.Count > 0) {
int levelSize = q.Count;
var levelArr = new List();
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;
}
}
