LeetCode 题解工作台
二叉树的层序遍历
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。 示例 1： 输入： root = [3,9,20,null,null,15,7] 输出： [[3],[9,20],[15,7]] 示例 2： 输入： root = [1] 输出： [[1]] 示例 3…
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们可以使用 BFS 的方法来解决这道题。首先将根节点入队，然后不断地进行以下操作，直到队列为空： - 遍历当前队列中的所有节点，将它们的值存储到一个临时数组 中，然后将它们的孩子节点入队。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[3],[9,20],[15,7]]
示例 2：
输入：root = [1] 输出：[[1]]
示例 3：
输入：root = [] 输出：[]
提示：
- 树中节点数目在范围
[0, 2000]内 -1000 <= Node.val <= 1000
解题思路
方法一：BFS
我们可以使用 BFS 的方法来解决这道题。首先将根节点入队，然后不断地进行以下操作，直到队列为空：
- 遍历当前队列中的所有节点，将它们的值存储到一个临时数组 中，然后将它们的孩子节点入队。
- 将临时数组 存储到答案数组中。
最后返回答案数组即可。
时间复杂度 ，空间复杂度 。其中 是二叉树的节点个数。
# 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]]:
ans = []
if root is None:
return ans
q = deque([root])
while q:
t = []
for _ in range(len(q)):
node = q.popleft()
t.append(node.val)
if node.left:
q.append(node.left)
if node.right:
q.append(node.right)
ans.append(t)
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you understand how to perform BFS traversal using a queue?
- question_mark
Can you explain why BFS is appropriate for this problem?
- question_mark
Are you able to handle edge cases like an empty tree or a tree with a single node?
常见陷阱
外企场景- error
Misunderstanding the level order traversal concept and treating it as a depth-first traversal.
- error
Failing to properly manage the queue to ensure that nodes are processed level by level.
- error
Not accounting for edge cases such as an empty tree or single-node tree, which require special handling.
进阶变体
外企场景- arrow_right_alt
Spiral Level Order Traversal
- arrow_right_alt
Zigzag Level Order Traversal
- arrow_right_alt
Reverse Level Order Traversal