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.
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.