Solution Explanation: 107. Binary Tree Level Order Traversal II

This problem asks for a bottom-up level order traversal of a binary tree. This means we need to traverse the tree level by level, starting from the leaves and working our way up to the root. A standard Breadth-First Search (BFS) algorithm can achieve a level order traversal, but we need to adapt it slightly to reverse the order.

Approach:

1. Initialization: We use a queue (q) to store nodes for BFS, and an array (ans) to store the levels of the tree.

2. BFS Traversal:

   • The queue is initially populated with the root node.
   • While the queue is not empty, we process one level at a time.
   • For each level, we create a temporary array (t) to store the node values of that level.
   • We iterate through the current queue size. This is crucial because the queue size changes as we add children.
   • For each node in the current level, we add its value to t, and then add its children to the end of q.
   • After processing all nodes on a level, we add t to ans.

3. Reversal: Finally, we reverse ans to achieve the bottom-up order.

Time Complexity: O(N), where N is the number of nodes in the tree. Each node is visited and processed exactly once.

Space Complexity: O(W), where W is the maximum width (maximum number of nodes) of the tree. This is because the queue can hold at most W nodes at any given time. In the worst case (a complete binary tree), W is proportional to N, so space complexity can also be considered O(N).

Code Examples:

The provided solutions demonstrate this approach in several programming languages. Let's break down the core logic using the Python example:

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        ans = []
        if root is None:
            return ans
        q = deque([root])  # Initialize queue with root
        while q:
            t = []           # Temporary array for current level
            for _ in range(len(q)):  # Process nodes for current level
                node = q.popleft()
                t.append(node.val)
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            ans.append(t)     # Add level to ans
        return ans[::-1]     # Reverse ans for bottom-up order

The Java, C++, Go, TypeScript, Rust, and Javascript examples follow a very similar structure, adapting the data structures and syntax specific to each language. The core BFS logic and final reversal remain consistent across all implementations.