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:

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
评论需要 JavaScript。