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).

https://leetcode.com/problems/binary-tree-level-order-traversal/

Example 1:

case1

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

Example 2:

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

Example 3:

Input: root = []
Output: []

Constraints:

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

Test Cases

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:

solution_test.py

import pytest

import os
import sys
sys.path.append(os.path.dirname(os.path.dirname(__file__)))
from _utils.binary_tree import build_tree
from solution import Solution

null = None


@pytest.mark.parametrize('root, expected', [
    ([3,9,20,null,null,15,7], [[3],[9,20],[15,7]]),
    ([1], [[1]]),
    ([], []),
])
class Test:
    def test_solution(self, root, expected):
        sol = Solution()
        assert sol.levelOrder(build_tree(root)) == expected

Thoughts

直接按层序（level-order）遍历，可以用队列加循环。待处理的节点加入队列时，同时把该节点的层数一起放入队列。节点的层数等于其父节点的层数加一。

Code

solution.py

from collections import deque
from typing import Optional


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


class Solution:
    def levelOrder(self, root: Optional[TreeNode]) -> list[list[int]]:
        values = []
        queue = deque()
        queue.append((root, 0))
        while len(queue) > 0:
            root, level = queue.popleft()
            if root is None: continue

            if level >= len(values):
                values.append([])
            values[-1].append(root.val)

            queue.append((root.left, level + 1))
            queue.append((root.right, level + 1))

        return values