Binary Tree Level Order Traversal II

Intuition

The bottom-up requirement is just a presentation twist on plain level-order traversal, so the core work is a normal breadth-first search. Keep a queue seeded with the root, and repeatedly process the queue one full level at a time by snapshotting its current size before draining it. Everything popped during that snapshot belongs to the same depth, and their children become the next level. Collect each level's values into a list and append it in top-down order. Once the traversal finishes, reversing the outer list (or inserting each level at the front as you go) flips the order to bottom-up.

Algorithm walkthrough

1. 1If the root is null, return an empty list since there are no levels to report.
2. 2Initialize a queue containing the root and an empty results list.
3. 3While the queue is not empty, record its size; that many nodes make up the current level.
4. 4Pop exactly that many nodes, appending each value to a fresh level list and enqueuing any non-null children for the next round.
5. 5Append the completed level list to the results in the natural top-down order.
6. 6After the loop ends, reverse the results list so the deepest level comes first, then return it.

Implementation

from collections import deque

class Solution:
    def levelOrderBottom(self, root: 'TreeNode') -> list[list[int]]:
        if root is None:
            return []
        result = []
        queue = deque([root])
        while queue:
            level = []
            for _ in range(len(queue)):
                node = queue.popleft()
                level.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            result.append(level)
        result.reverse()
        return result