题目描述

[EN | CN]

给你一个二叉树,请你返回其按 层序遍历 得到的结点值(即逐层地,从左到右访问所有结点)。

示例:

二叉树:[3, 9, 20, null, null, 15, 7]

1
2
3
4
5
3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果:

1
2
3
4
5
[
  [3],
  [9,20],
  [15,7]
]

解法 1:逐层迭代

当遍历第 $k$ 层的时候,将该层所有结点的子结点(即 $k + 1$ 层)都放入一个新的数组中,遍历完当前层就往下一层遍历。

假设一共 $n$ 个结点,那么

  • 时间复杂度为 $O(n)$,遍历一遍;
  • 空间复杂度为 $O(n)$,需要保存下一层的结点。

实现与结果如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if root is None:
            return []

        curr_level = []
        next_level = [root]
        ret = []

        while len(next_level) > 0:
            curr_level = next_level
            next_level = []
            ret.append([])
            for node in curr_level:
                ret[-1].append(node.val)
                if node.left is not None:
                    next_level.append(node.left)
                if node.right is not None:
                    next_level.append(node.right)

        return ret
  • 执行用时:40 ms,在所有 Python3 提交中击败了 65.04% 的用户。
  • 内存消耗:13.9 MB,在所有 Python3 提交中击败了 5.25% 的用户。