Binary Tree Level Order Traversal

Problem Id: 102 Difficulty: Medium Tag: Tree Tag: Breadth-first Search


Intuition

The order of Breadth-first Search is just the level order of the binary tree. Since each level should be separated in the result, we should use something to mark the level. (None in this solution)

Solution


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


class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []
        level = 0
        queue = deque([root, None])
        ans = []
        while len(queue) > 1:
            p = queue.popleft()
            if p is None:
                queue.append(None)
                level += 1
                continue
            if level >= len(ans):
                ans.append([])
            ans[level].append(p.val)
            if p.left:
                queue.append(p.left)
            if p.right:
                queue.append(p.right)
        return ans