Dare2Solve
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).
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.
Breadth-First Search (BFS):
Reverse the Result:
(O(n)), where n
is the number of nodes in the tree. Each node is visited once during the BFS.
(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.
class Solution {
public:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
if (!root) return {};
vector<vector<int>> levels;
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
vector<int> 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;
}
};
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]
class Solution {
public List<List<Integer>> levelOrderBottom(TreeNode root) {
List<List<Integer>> levels = new ArrayList<>();
if (root == null) return levels;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while (!queue.isEmpty()) {
int levelSize = queue.size();
List<Integer> 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;
}
}
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();
};