Description:
Given the root of a binary tree, return the bottom-up level order traversal of its nodes’ values. (i.e., from left to right, level by level from leaf to root).
Examples:
Example 1:
Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]
Example 2:
Input: root = [1]
Output: [[1]]
Example 3:
Input: root = []
Output: []Solution in Python:
To solve the problem of returning the bottom-up level order traversal of a binary tree, we can use a breadth-first search (BFS) approach. We’ll traverse the tree level by level from top to bottom, and then reverse the order of the levels to get the bottom-up order.
Python
from collections import deque
from typing import List, Optional
class Solution:
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
# Initialize a queue for BFS
queue = deque([root])
result = []
while queue:
level_size = len(queue)
current_level = []
# Iterate over all nodes at the current level
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
# Add the child nodes of the current node to the queue
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# Append the current level at the beginning of the result list
result.insert(0, current_level)
return resultExplanation:
- Initialization:
- We check if the root is
None. If it is, we return an empty list since there are no nodes to traverse. - We initialize a queue using
collections.dequeand add the root node to it. - We also initialize an empty list
resultto store the levels of nodes.
- We check if the root is
- Breadth-First Search (BFS):
- We perform a BFS using a while loop that continues until the queue is empty.
- For each level, we determine the number of nodes (
level_size) currently in the queue. - We initialize a list
current_levelto store the values of nodes at the current level.
- Processing Each Level:
- We iterate over all nodes at the current level using a for loop.
- For each node, we dequeue it from the front of the queue, add its value to
current_level, and enqueue its left and right children (if they exist).
- Storing the Current Level:
- After processing all nodes at the current level, we insert
current_levelat the beginning of theresultlist. This ensures that the final result is in bottom-up order.
- After processing all nodes at the current level, we insert
- Return Result:
- Once the BFS is complete and all levels are processed, we return the
resultlist which now contains the bottom-up level order traversal of the tree.
- Once the BFS is complete and all levels are processed, we return the
This solution ensures that we traverse the tree level by level and store the nodes’ values in the correct bottom-up order, fulfilling the problem’s requirements efficiently.
Solution in Javascript:
JavaScript
/**
* @param {TreeNode} root
* @return {number[][]}
*/
var levelOrderBottom = function(root) {
// If the root is null, return an empty array since there are no nodes to traverse
if (!root) return [];
// Initialize a queue for BFS and add the root node to it
let queue = [];
queue.push(root);
// Initialize an empty array to store the levels of nodes
let result = [];
// Perform BFS until the queue is empty
while (queue.length > 0) {
// Determine the number of nodes at the current level
let levelSize = queue.length;
// Initialize an array to store the values of nodes at the current level
let currentLevel = [];
// Iterate over all nodes at the current level
for (let i = 0; i < levelSize; i++) {
// Dequeue the front node in the queue
let node = queue.shift();
// Add the node's value to the current level array
currentLevel.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 beginning of the result array
result.unshift(currentLevel);
}
// Return the result array containing the bottom-up level order traversal
return result;
};Solution in Java:
Java
import java.util.*;
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
// Initialize the result list that will store the levels from bottom to top
List<List<Integer>> result = new LinkedList<>();
// If the root is null, return the empty result list
if (root == null) {
return result;
}
// Initialize a queue for BFS and add the root node to it
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
// Perform BFS until the queue is empty
while (!queue.isEmpty()) {
// Determine the number of nodes at the current level
int levelSize = queue.size();
// Initialize an array to store the values of nodes at the current level
List<Integer> currentLevel = new ArrayList<>();
// Iterate over all nodes at the current level
for (int i = 0; i < levelSize; i++) {
// Dequeue the front node in the queue
TreeNode node = queue.poll();
// Add the node's value to the current level list
currentLevel.add(node.val);
// Enqueue the left child if it exists
if (node.left != null) {
queue.add(node.left);
}
// Enqueue the right child if it exists
if (node.right != null) {
queue.add(node.right);
}
}
// Add the current level list to the beginning of the result list
result.add(0, currentLevel);
}
// Return the result list containing the bottom-up level order traversal
return result;
}
}Solution in C#:
C#
using System.Collections.Generic;
public class Solution {
public IList<IList<int>> LevelOrderBottom(TreeNode root) {
// Initialize the result list that will store the levels from bottom to top
IList<IList<int>> result = new List<IList<int>>();
// If the root is null, return the empty result list
if (root == null) {
return result;
}
// Initialize a queue for BFS and add the root node to it
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
// Perform BFS until the queue is empty
while (queue.Count > 0) {
// Determine the number of nodes at the current level
int levelSize = queue.Count;
// Initialize a list to store the values of nodes at the current level
IList<int> currentLevel = new List<int>();
// Iterate over all nodes at the current level
for (int i = 0; i < levelSize; i++) {
// Dequeue the front node in the queue
TreeNode node = queue.Dequeue();
// Add the node's value to the current level list
currentLevel.Add(node.val);
// Enqueue the left child if it exists
if (node.left != null) {
queue.Enqueue(node.left);
}
// Enqueue the right child if it exists
if (node.right != null) {
queue.Enqueue(node.right);
}
}
// Insert the current level list at the beginning of the result list
result.Insert(0, currentLevel);
}
// Return the result list containing the bottom-up level order traversal
return result;
}
}