Medium

Binary Tree Level Order Traversal

024

Given a binary tree encoded as level-order with -100000 as null, return level order traversal as a list of levels.

EXAMPLES

Example 1

Input
{
  "root": [
    3,
    9,
    20,
    -100000,
    -100000,
    15,
    7
  ]
}

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

FUNCTION SHAPE

root: intArray→intMatrix

SOLUTION NOTE

BFS on a tree. w is the maximum width (max nodes at any level). Process all nodes at current level before moving to next level.

Reveal reference solution +

pythonREFERENCE

def levelOrder(self, root: TreeNode) -> List[List[int]]:
    if not root:
        return []

    res = []
    q = deque([root])

    while q:
        level = []
        for _ in range(len(q)):
            node = q.popleft()
            level.append(node.val)
            if node.left:
                q.append(node.left)
            if node.right:
                q.append(node.right)
        res.append(level)

    return res

TimeO(n)

SpaceO(w)

Open on LeetCode ↗