107. Binary Tree Level Order Traversal II

Check out the problem description here.

Binary Tree Level Order Traversal II - LeetCode

Solution

Approach 1:

Using the queue

This can be done using the same apporach we followed in the first part of this problem (leetcode 102). Click the below link for the same.

102. Binary Tree Level Order Traversal

After getting the result , we can reverse it to get the required result.

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        res=[]
        q=[]
        
        if root : q.append(root)
        while(q):
            size=len(q)
            inter=[]
            for i in range(size):
                r=q.pop(0)
                inter.append(r.val)
                if(r.left):
                    q.append(r.left)
                if(r.right):
                    q.append(r.right)    
            res.append(inter)
            
        return res[::-1]

Time :O(n)

Space :O(n)

Approach 2:

If you want to avoid the time spent on reversing the queue. One way that can be solved is using a deque. In this we traverse the tree in the usual level by level order from top , but the list of nodes in each level is enqued at the front of the dequeue. At the end the deque is returned.

from collections import deque
class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        deq=deque()
        q=[]
        
        if root : q.append(root)
        while(q):
            size=len(q)
            inter=[]
            for i in range(size):
                r=q.pop(0)
                inter.append(r.val)
                if(r.left):
                    q.append(r.left)
                if(r.right):
                    q.append(r.right)    
            deq.appendleft(inter)
            
        return deq

Time :O(n)

Space :O(n)