Description:
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]]
Example 3:
Input: root = []
Output: []Solution in Python:
To solve the problem of returning the level order traversal of a binary tree’s nodes’ values in Python, we can use a breadth-first search (BFS) approach. This involves using a queue to keep track of the nodes at each level as we traverse the tree.
Python
from collections import deque
from typing import List, Optional
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
# If the tree is empty, return an empty list
if not root:
return []
# Initialize the result list and the queue for BFS
result = []
queue = deque([root])
while queue:
# List to store nodes at the current level
level = []
# Number of nodes at the current level
level_length = len(queue)
for _ in range(level_length):
# Dequeue a node from the front of the queue
node = queue.popleft()
# Add the node's value to the current level list
level.append(node.val)
# Enqueue the left child if it exists
if node.left:
queue.append(node.left)
# Enqueue the right child if it exists
if node.right:
queue.append(node.right)
# Add the current level list to the result list
result.append(level)
return resultExplanation:
- Initialization:
- Import the necessary modules:
dequefromcollectionsfor efficient queue operations andListandOptionalfromtypingfor type hints. - Check if the root is
None. If it is, return an empty list as there are no levels to traverse. - Initialize an empty list
resultto store the level order traversal. - Initialize a queue
queueusingdequeand enqueue the root node.
- Import the necessary modules:
- Breadth-First Search (BFS) Loop:
- The while loop continues until the queue is empty.
- For each level, initialize an empty list
levelto store the nodes’ values at the current level. - Determine the number of nodes at the current level using
level_length = len(queue).
- Processing Each Level:
- For each node in the current level, dequeue a node from the front of the queue.
- Add the node’s value to the
levellist. - Enqueue the node’s left child if it exists.
- Enqueue the node’s right child if it exists.
- Storing the Level:
- After processing all nodes at the current level, add the
levellist to theresultlist.
- After processing all nodes at the current level, add the
- Return the Result:
- Once all levels have been processed, return the
resultlist, which contains the level order traversal of the binary tree.
- Once all levels have been processed, return the
This implementation ensures that each level of the tree is processed in order, and the nodes’ values are collected level by level from left to right.
Solution in Javascript:
JavaScript
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrder = function(root) {
// If the tree is empty, return an empty array
if (!root) {
return [];
}
// Initialize the result array and the queue for BFS
const result = [];
const queue = [root];
// While there are nodes to process in the queue
while (queue.length > 0) {
// Array to store nodes' values at the current level
const level = [];
// Number of nodes at the current level
const levelLength = queue.length;
// Process each node at the current level
for (let i = 0; i < levelLength; i++) {
// Dequeue a node from the front of the queue
const node = queue.shift();
// Add the node's value to the current level array
level.push(node.val);
// Enqueue the left child if it exists
if (node.left) {
queue.push(node.left);
}
// Enqueue the right child if it exists
if (node.right) {
queue.push(node.right);
}
}
// Add the current level array to the result array
result.push(level);
}
return result;
};Solution in Java:
Java
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
// Initialize the result list to store the levels of the binary tree
List<List<Integer>> result = new ArrayList<>();
// If the root is null, return an empty list
if (root == null) {
return result;
}
// Initialize a queue to facilitate BFS
Queue<TreeNode> queue = new LinkedList<>();
// Add the root node to the queue as the starting point
queue.add(root);
// Continue processing nodes while the queue is not empty
while (!queue.isEmpty()) {
// List to store the values of nodes at the current level
List<Integer> level = new ArrayList<>();
// Get the number of nodes at the current level
int levelSize = queue.size();
// Process each node at the current level
for (int i = 0; i < levelSize; i++) {
// Remove the front node from the queue
TreeNode currentNode = queue.poll();
// Add the value of the current node to the level list
level.add(currentNode.val);
// If the current node has a left child, add it to the queue
if (currentNode.left != null) {
queue.add(currentNode.left);
}
// If the current node has a right child, add it to the queue
if (currentNode.right != null) {
queue.add(currentNode.right);
}
}
// Add the current level list to the result list
result.add(level);
}
// Return the result list containing the level order traversal
return result;
}
}Solution in C#:
C#
using System;
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> LevelOrder(TreeNode root) {
// Initialize the result list to store the levels of the binary tree
IList<IList<int>> result = new List<IList<int>>();
// If the root is null, return an empty list
if (root == null) {
return result;
}
// Initialize a queue to facilitate BFS
Queue<TreeNode> queue = new Queue<TreeNode>();
// Add the root node to the queue as the starting point
queue.Enqueue(root);
// Continue processing nodes while the queue is not empty
while (queue.Count > 0) {
// List to store the values of nodes at the current level
List<int> level = new List<int>();
// Get the number of nodes at the current level
int levelSize = queue.Count;
// Process each node at the current level
for (int i = 0; i < levelSize; i++) {
// Remove the front node from the queue
TreeNode currentNode = queue.Dequeue();
// Add the value of the current node to the level list
level.Add(currentNode.val);
// If the current node has a left child, add it to the queue
if (currentNode.left != null) {
queue.Enqueue(currentNode.left);
}
// If the current node has a right child, add it to the queue
if (currentNode.right != null) {
queue.Enqueue(currentNode.right);
}
}
// Add the current level list to the result list
result.Add(level);
}
// Return the result list containing the level order traversal
return result;
}
}