🎨Now live: Try our Free AI Image Generation Feature

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).
Intuition
The problem requires a level order traversal, but instead of starting from the root, the final output should be from the bottom-most level to the top. This suggests that a regular level order traversal can be performed, but the result should be reversed before returning it.
Approach
- Breadth-First Search (BFS): - Use a queue to perform BFS, which allows processing the tree level by level. - Start by adding the root node to the queue. - While the queue is not empty, process each level by iterating over the nodes currently in the queue. - For each node, record its value, and add its left and right children to the queue for processing in the next iteration. - Store the values of each level in a list.
- Reverse the Result: - Once all levels have been processed and stored in a list of lists, reverse the list to get the bottom-up order. - Return the reversed list as the final result.
Complexity
Time Complexity:
(O(n)), where n
is the number of nodes in the tree. Each node is visited once during the BFS.
Space Complexity:
(O(n)), where n
is the number of nodes. This is due to the space required to store the output list and the queue used for BFS.
Code
C++
class Solution {
public:
vector> levelOrderBottom(TreeNode* root) {
if (!root) return {};
vector> levels;
queue q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
vector level;
for (int i = 0; i < levelSize; ++i) {
TreeNode* currentNode = q.front();
q.pop();
if (currentNode->left) q.push(currentNode->left);
if (currentNode->right) q.push(currentNode->right);
level.push_back(currentNode->val);
}
levels.push_back(level);
}
reverse(levels.begin(), levels.end());
return levels;
}
};
Python
class Solution:
def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
if not root:
return []
levels = []
queue = deque([root])
while queue:
level = []
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
level.append(node.val)
levels.append(level)
return levels[::-1]
Java
class Solution {
public List> levelOrderBottom(TreeNode root) {
List> levels = new ArrayList<>();
if (root == null) return levels;
Queue queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List level = new ArrayList<>();
for (int i = 0; i < levelSize; i++) {
TreeNode currentNode = queue.poll();
if (currentNode.left != null) queue.add(currentNode.left);
if (currentNode.right != null) queue.add(currentNode.right);
level.add(currentNode.val);
}
levels.add(level);
}
Collections.reverse(levels);
return levels;
}
}
JavaScript
const levelOrderBottom = (root) => {
if (!root) return [];
const levels = [];
const queue = [root];
while (queue.length) {
const level = [];
const queueLength = queue.length;
for (let i = 0; i < queueLength; i++) {
const currentNode = queue.shift();
if (currentNode.left) queue.push(currentNode.left);
if (currentNode.right) queue.push(currentNode.right);
level.push(currentNode.val)
}
levels.push(level);
}
return levels.reverse();
};