Given the root
of a binary tree, write a function to return the bottom-up level order traversal of its nodes' values.
In other words, the traversal should proceed level by level from the leaf nodes up to the root node. For each level, the nodes should be traversed from left to right.
Example 1:
Suppose you have the following binary tree:
3
/ \
9 20
/ \
15 7
The expected output would be:
[[15, 7], [9, 20], [3]]
Example 2:
Consider a binary tree with only the root node:
1
The expected output would be:
[[1]]
Example 3:
Now, suppose the binary tree is empty:
None
The expected output would be:
[]
Clarifications/Constraints:
None
?Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. This means traversing the tree level by level from leaf to root (i.e., from the bottom to the top).
A straightforward approach is to perform a standard level order traversal (breadth-first search) and then reverse the resulting list of lists. This involves:
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrderBottom(root):
if not root:
return []
queue = deque([root])
levels = []
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
levels.append(current_level)
return levels[::-1] # Reversing the levels list
levels
list can store all nodes.An optimal approach avoids the explicit reversal step by inserting each level's nodes at the beginning of the result list. This maintains the bottom-up order as we traverse.
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrderBottomOptimal(root):
if not root:
return []
queue = deque([root])
levels = []
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
levels.insert(0, current_level) # Insert at the beginning
return levels
levels
list stores all node values.The optimal approach provides a cleaner solution by directly building the bottom-up level order traversal without a separate reversal step. Both approaches maintain O(N) time and space complexity, but the optimal approach is slightly more efficient due to avoiding the extra reversal operation.