Binary Tree Level Order Traversal

Question

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

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]
]

Tags

• Tree
• BFS

Thought

Use BFS search for all the nodes. In order to confirm the level of each node, we can add the level with the node together in the queue for BFS.

Code

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def levelOrder(self, root):
        """
        Use BFS search
        :type root: TreeNode
        :rtype: List[List[int]]
        """
        result = []
        if root is None:
            return result
        queue = [(0, root)]
        while queue:
            level, ptr = queue.pop(0)
            if ptr.left is not None:
                queue.append((level + 1, ptr.left))
            if ptr.right is not None:
                queue.append((level + 1, ptr.right))
            if len(result) == level:
                result.append([ptr.val])
            else:
                result[level] += [ptr.val]
        return result