102. Binary Tree Level Order Traversal

Problem¶

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

Example 1:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7|3],[9,20],[15,7]]

Example 2:

Input: root = [1]
Output: [[1|1]]

Example 3:

Input: root = []
Output: []

Constraints:

The number of nodes in the tree is in the range [0, 2000].
-1000 <= Node.val <= 1000

Solve¶

Recursive¶

O(n)

I do exactly what the problem said:

Create a array result
Loop through all nodes in the root tree, while keeping its level using recursive
Push them in to result as we go

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []

        def helper(root, level = None):
            if level is None:
                level = 0

            while len(result) - 1 < level:
                result.append([])

            result[level].append(root.val)
            if root.left:
                helper(root.left, level + 1)
            if root.right:
                helper(root.right, level + 1)
        if root:
            helper(root)
        return result

Using queue¶

O(n)

Simple BFS implement with queue

class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
        result = []

        q = []
        if root:
            q.append((root,0))

        while len(q) > 0:
            r, level = q.pop(0)

            if len(result) - 1 < level:
                result.append([])

            result[level].append(r.val)
            if r.left:
                q.append((r.left, level + 1))
            if r.right:
                q.append((r.right, level + 1))
        return result

Last update : September 17, 2023
Created : August 16, 2023