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.
1using System.Collections.Generic;
2
3public class TreeNode {
4 public int val;
5 public TreeNode left;
public TreeNode right;
public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
this.val = val;
this.left = left;
this.right = right;
}
}
public class Solution {
public IList<IList<int>> LevelOrderBottom(TreeNode root) {
List<IList<int>> result = new List<IList<int>>();
AddToLevel(root, 0, result);
result.Reverse();
return result;
}
private void AddToLevel(TreeNode node, int level, List<IList<int>> result) {
if (node == null) return;
if (result.Count == level) {
result.Add(new List<int>());
}
result[level].Add(node.val);
AddToLevel(node.left, level + 1, result);
AddToLevel(node.right, level + 1, result);
}
}The C# solution makes use of a private helper method `AddToLevel` in a similar recursive manner as the JavaScript solution. The recursive helper adds nodes to a level-based result list, creating the right level structure before the list is reversed at the end.