https://leetcode.com/problems/binary-tree-level-order-traversal-ii

Not the most optimal way, but for me the most intuitive is to use bfs traversal of our graph, put all information into some auxilary list, and then traverse this list and reconstruct output. Let us consider the following example in more details:

image

  1. Out_temp is temporary list with pairs: first element in pair is value of node and the second is level of this node. We use bfs with queue to traverse our tree and in the end we have Out_temp = [[3, 0], [9, 1], [20, 1], [15, 2], [7, 2]].
  2. The second step is to reconstruct level by level Out list: we traverse our Out_temp and if level of new element is not the same as previous, we create new sublist.

Complexity is O(V), where V is number of nodes in our tree, because we use bfs traversal and then we have one more O(V) postprosessing of our data. Space complexity is also O(V).

class Solution:
    def levelOrderBottom(self, root):
        if not root: return []
    
        Out_temp, deq = [], deque([[root, 0]])
    
        while deq:
            elem = deq.popleft()
            Out_temp.append([elem[0].val, elem[1]])
            if elem[0].left:
                deq.append([elem[0].left, elem[1] + 1])
            if elem[0].right:
                deq.append([elem[0].right, elem[1] + 1])

        Out = [[Out_temp[0][0]]]
        for i in range(1, len(Out_temp)):
            if Out_temp[i][1] == Out_temp[i-1][1]:
                Out[Out_temp[i][1]].append(Out_temp[i][0])
            else:
                Out.append([Out_temp[i][0]])

        return Out[::-1]

If you like the solution, you can upvote it on leetcode discussion section: Problem 0107