Sponsored
Sponsored
This approach utilizes a queue to perform a standard level order traversal but stores each level of nodes in a separate list. After the traversal, the entire list of lists is reversed to provide the bottom-up level order.
Time Complexity: O(n) where n is the number of nodes, as each node is processed once.
Space Complexity: O(n) for storing the queue and the result.
1import java.util.*;
2
3class TreeNode {
4 int val;
5 TreeNode left;
6 TreeNode right;
7 TreeNode(int x) { val = x; }
8}
9
10class Solution {
11 public List<List<Integer>> levelOrderBottom(TreeNode root) {
12 List<List<Integer>> result = new LinkedList<>();
13 if (root == null) return result;
14
15 Queue<TreeNode> queue = new LinkedList<>();
16 queue.offer(root);
17 while (!queue.isEmpty()) {
18 int levelSize = queue.size();
19 List<Integer> currentLevel = new ArrayList<>();
20 for (int i = 0; i < levelSize; i++) {
21 TreeNode currentNode = queue.poll();
22 currentLevel.add(currentNode.val);
23 if (currentNode.left != null) queue.offer(currentNode.left);
24 if (currentNode.right != null) queue.offer(currentNode.right);
25 }
26 result.add(0, currentLevel);
27 }
28
29 return result;
30 }
31}The Java solution uses a `Queue` for level order traversal similar to BFS. Instead of reversing the final result, each level is added at the beginning of the results list, achieving a bottom-up order directly.
This recursive approach traverses the tree, keeping track of the depth of each node. Nodes are added to sublists based on their depth, and the list of lists is reversed at the end to provide bottom-up level order.
Time Complexity: O(n) where n is the number of nodes.
Space Complexity: O(n) for the recursion stack and result storage.
1function TreeNode(val) {
2 this.
In this JavaScript solution, a helper function `addToLevel` is used. It traverses the tree recursively. Each node's value is added to a sublist that corresponds to its depth, creating a level-wise list of nodes, which is then reversed to achieve the bottom-up order.