deepSWE.io

Binary Tree Level Order Traversal II

TreesBFS

Problem Statement

Given the `root` of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., from left to right, level by level from leaf to root).

Example

Output: [[15, 7], [9, 20], [3]]

Algorithm Explanation

We can solve this problem using a breadth-first search (BFS) approach. We'll traverse the tree level by level, and at the end, we'll reverse the result.

Algorithm Steps

Queue: We'll use a queue to perform a level-order traversal. We start by adding the root to the queue.
Level Traversal: While the queue is not empty, we process all nodes at the current level. We can find the number of nodes at the current level by taking the size of the queue.
Store Levels: We'll have a list of lists to store the nodes at each level. For each level, we create a new list and add the values of the nodes at that level.
Enqueue Children: As we process each node, we enqueue its left and right children to be processed in the next level.
Reverse Result: After the traversal is complete, we reverse the list of lists to get the bottom-up level order.

Start

Adding root to the queue.

Queue

Result

[15, 7]

[9, 20]

[3]

Binary Tree Level Order Traversal II Solution


from collections import deque

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return []
        
        result = []
        queue = deque([root])
        
        while queue:
            level_size = len(queue)
            level = []
            for _ in range(level_size):
                node = queue.popleft()
                level.append(node.val)
                
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            
            result.append(level)
            
        return result[::-1]