LeetCode 题解工作台
二叉树的层序遍历 II
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历） 示例 1： 输入： root = [3,9,20,null,null,15,7] 输出： [[15,7],[9,20],[3]] 示例 2： 输入： root = [1]…
3
题型
7
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
我们可以使用 BFS 的方法来解决这道题。首先将根节点入队，然后不断地进行以下操作，直到队列为空： - 遍历当前队列中的所有节点，将它们的值存储到一个临时数组 中，然后将它们的孩子节点入队。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
示例 1：
输入：root = [3,9,20,null,null,15,7] 输出：[[15,7],[9,20],[3]]
示例 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 levelOrderBottom(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[::-1]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you maintain left-to-right order within each level while collecting nodes?
- question_mark
Can you handle empty trees or single-node trees without extra logic errors?
- question_mark
Will you reverse the levels efficiently without disrupting the BFS ordering?
常见陷阱
外企场景- error
Prepending each level incorrectly and reversing individual node lists instead of the level list, causing misordered bottom-up traversal.
- error
Failing to account for null children, which can lead to missing nodes or misalignment between parent and child levels.
- error
Using a top-down approach and forgetting to reverse the final result, giving standard level order instead of the required bottom-up output.
进阶变体
外企场景- arrow_right_alt
Binary Tree Level Order Traversal I: Standard top-down level order without reversing, useful for comparing BFS ordering logic.
- arrow_right_alt
Zigzag Level Order Traversal: Alternate left-to-right and right-to-left traversal at each level, combining BFS with direction tracking.
- arrow_right_alt
Right Side View of Binary Tree: Only collect the rightmost node at each level, which modifies BFS level tracking to selective node capture.