1 minute read

107. Binary Tree Level Order Traversal II

Difficulty: Medium

Related Topics: Tree, BFS, Binary Tree

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 1:

Input: root = [3,9,20,null,null,15,7] Output: [[15,7],[9,20],[3]]

Example 2:

Input: root = [1] Output: [[1]]

Example 3:

Input: root = [] Output: []

Code:

from collections import deque
class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        myq = deque()
        ans = []
        save = []
        temp = 0
        if not root:
            return ans
        myq.append((root, 0))
        while myq:
            curr, level = myq.popleft()
            if temp == level:
                save.append(curr.val)
            else:
                ans.append(save)
                save=[]
                save.append(curr.val)
                temp+=1

            if curr:
                if curr.left:
                    myq.append((curr.left, level+1))
                if curr.right:
                    myq.append((curr.right, level+1))
                    
        ans.append(save)
        return ans[::-1]

Feedbacks:

I used BFS to level-order traverse the tree and deque to store the values of current root. I used an extra list to store the values on the same levels. Also made a level indicator. So when level indicater is same as current level, I add values to the temporary list, else, I add temporary list to the answer list and initialize the temporary list, increment a level indicator by one. And at the end, I reverse the answer list before I return answer.

You may also enjoy