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.
1from collections import deque
2
3class TreeNode:
4 def __init__(self, val=0, left=None, right=None):
5 self.val = val
6 self.left = left
7 self.right = right
8
9class Solution:
10 def levelOrderBottom(self, root: TreeNode):
11 if not root:
12 return []
13
14 result, queue = [], deque([root])
15 while queue:
16 level_size = len(queue)
17 level_nodes = []
18 for _ in range(level_size):
19 node = queue.popleft()
20 level_nodes.append(node.val)
21 if node.left:
22 queue.append(node.left)
23 if node.right:
24 queue.append(node.right)
25 result.append(level_nodes)
26
27 return result[::-1]In this Python solution, we use a double-ended queue (`deque`) from the `collections` module for the traversal. A queue allows us to efficiently perform level order traversal, adding child nodes to the queue and processing them in FIFO order. After processing all levels, we invert the result list to provide a bottom-up output.
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;
6 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.