Leetcode 102. Binary Tree Level Order Traversal (Python)

Related Topic

Breadth-First-Search. Tree.

Description

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

Sample I/O

Example 1

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

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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

Methodology

This question can be solved by Breadth First Search.

The answer is very direct, use bfs to traversal level by level and for each level we loop through node and append them all to a tmp list, then we append the tmp list to the answer list and return. To apply FIFO, we can use deque for popleft()

Code(BFS)

def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if root is None: return []
        queue, res = collections.deque([root]),[]
        while queue:
            size = len(queue)
            tmp=[]
            while size>0: 
                node = queue.popleft()
                tmp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
                size-=1
            res.append(tmp)
        return res

BigO

We traversal all nodes level by level once so time complexity is O(n)