107. Binary Tree Level Order Traversal II (Python)

Related Topic

Breadth-First-Search.

Description

Given a binary tree, return the bottom-up level order traversal of its nodes’ values. (ie, from left to right, level by level from leaf to root).

Sample I/O

Example 1

For example: Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its bottom-up level order traversal as:

[
  [15,7],
  [9,20],
  [3]
]

Methodology

Use BFS to traversal the tree level by level, record each level and append to the result list, then reverse the result list

Code (BFS)

def levelOrderBottom(self, root: TreeNode) -> List[List[int]]:
        if not root: return []
        queue = collections.deque([root])
        res=[]
        while queue:
            tmp = []
            for i in range(len(queue)):
                node=queue.popleft()
                tmp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            res.append(tmp)
        return res[::-1]

BigO

We traversal all elements of the tree once so total time complexity is O(n)