Article / 文章
LeetCode 第107题：二叉树的层序遍历 II
给你二叉树的根节点 root ，返回其节点值 自底向上的层序遍历 。 （即按从叶子节点所在层到根节点所在的层，逐层从左到右遍历）
题目描述
给你二叉树的根节点 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
解题思路
方法：层序遍历 + 反转
这道题是第102题“二叉树的层序遍历”的变体，唯一的区别是要求自底向上返回层序遍历结果。
关键点：
- 先进行常规的层序遍历（从上到下）
- 最后将结果列表反转
- 也可以在遍历过程中将每层结果插入到结果列表的头部，避免最后的反转操作
具体步骤：
- 如果根节点为空，返回空列表
- 使用队列进行层序遍历：
- 将根节点入队
- 当队列不为空时，处理当前层的所有节点
- 记录当前层的节点值
- 将当前层节点的子节点入队
- 将最终结果列表反转（或在遍历过程中使用头插法）
- 返回结果
时间复杂度：O(n)，其中n是树中节点的数量 空间复杂度：O(n)，队列中最多存储n个节点
图解思路
层序遍历过程分析表
| 步骤 | 队列状态 | 当前层节点 | 当前结果 |
|---|---|---|---|
| 初始 | [3] | - | [] |
| 第1层 | [9,20] | [3] | [[3]] |
| 第2层 | [15,7] | [9,20] | [[3],[9,20]] |
| 第3层 | [] | [15,7] | [[3],[9,20],[15,7]] |
| 反转 | - | - | [[15,7],[9,20],[3]] |
两种实现方式对比
| 实现方式 | 遍历过程 | 最终处理 | 优缺点 |
|---|---|---|---|
| 反转法 | 常规层序遍历 | 反转整个结果列表 | 实现简单，需要额外的反转操作 |
| 头插法 | 常规层序遍历 | 每层结果插入到结果列表头部 | 无需最后反转，但插入操作可能较慢 |
代码实现
C# 实现
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
// 方法一：层序遍历后反转结果
public IList<IList<int>> LevelOrderBottom(TreeNode root) {
List<IList<int>> result = new List<IList<int>>();
if (root == null) {
return result;
}
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Count > 0) {
int levelSize = queue.Count;
List<int> currentLevel = new List<int>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.Dequeue();
currentLevel.Add(node.val);
if (node.left != null) {
queue.Enqueue(node.left);
}
if (node.right != null) {
queue.Enqueue(node.right);
}
}
result.Add(currentLevel);
}
// 反转结果列表
result.Reverse();
return result;
}
// 方法二：使用头插法
public IList<IList<int>> LevelOrderBottomInsertAtHead(TreeNode root) {
LinkedList<IList<int>> result = new LinkedList<IList<int>>();
if (root == null) {
return result.ToList();
}
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
while (queue.Count > 0) {
int levelSize = queue.Count;
List<int> currentLevel = new List<int>();
for (int i = 0; i < levelSize; i++) {
TreeNode node = queue.Dequeue();
currentLevel.Add(node.val);
if (node.left != null) {
queue.Enqueue(node.left);
}
if (node.right != null) {
queue.Enqueue(node.right);
}
}
// 在结果列表头部添加当前层
result.AddFirst(currentLevel);
}
return result.ToList();
}
}Python 实现
# 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]]:
result = []
if not root:
return result
from collections import deque
queue = deque([root])
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(current_level)
# 反转结果列表
return result[::-1]
# 方法二：使用头插法
def levelOrderBottomInsertAtHead(self, root: Optional[TreeNode]) -> List[List[int]]:
result = []
if not root:
return result
from collections import deque
queue = deque([root])
while queue:
level_size = len(queue)
current_level = []
for _ in range(level_size):
node = queue.popleft()
current_level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
# 在结果列表头部添加当前层
result.insert(0, current_level)
return resultC++ 实现
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
// 方法一：层序遍历后反转结果
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> result;
if (root == nullptr) {
return result;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
vector<int> currentLevel;
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
currentLevel.push_back(node->val);
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
}
result.push_back(currentLevel);
}
// 反转结果列表
reverse(result.begin(), result.end());
return result;
}
// 方法二：使用头插法
vector<vector<int>> levelOrderBottomInsertAtHead(TreeNode* root) {
vector<vector<int>> result;
if (root == nullptr) {
return result;
}
queue<TreeNode*> q;
q.push(root);
while (!q.empty()) {
int levelSize = q.size();
vector<int> currentLevel;
for (int i = 0; i < levelSize; i++) {
TreeNode* node = q.front();
q.pop();
currentLevel.push_back(node->val);
if (node->left != nullptr) {
q.push(node->left);
}
if (node->right != nullptr) {
q.push(node->right);
}
}
// 在结果列表头部添加当前层
result.insert(result.begin(), currentLevel);
}
return result;
}
};执行结果
C# 实现
- 执行用时：96 ms
- 内存消耗：41.2 MB
Python 实现
- 执行用时：36 ms
- 内存消耗：16.8 MB
C++ 实现
- 执行用时：4 ms
- 内存消耗：12.5 MB
性能对比
| 语言 | 执行用时 | 内存消耗 | 特点 |
|---|---|---|---|
| C# | 96 ms | 41.2 MB | 代码结构清晰，使用内置的Reverse方法 |
| Python | 36 ms | 16.8 MB | 使用切片操作[::-1]反转列表，简洁高效 |
| C++ | 4 ms | 12.5 MB | 执行效率最高，内存占用最小 |
代码亮点
- 🎯 利用队列实现高效的层序遍历
- 💡 提供两种实现方式：反转法和头插法
- 🔍 精确处理每一层的节点，确保层序关系正确
- 🎨 代码结构清晰，变量命名规范，易于理解
常见错误分析
- 🚫 忘记处理根节点为空的边界情况
- 🚫 层序遍历后忘记反转结果列表
- 🚫 使用头插法时，插入操作实现不正确
- 🚫 队列操作不当，导致层序关系混乱
解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 |
|---|---|---|---|---|
| 反转法 | O(n) | O(n) | 实现简单，直观 | 需要额外的反转操作 |
| 头插法 | O(n) | O(n) | 无需最后反转 | 插入操作可能较慢，尤其在数组实现中 |
| DFS递归 | O(n) | O(h) | 可直接构建结果 | 实现复杂，需要额外处理层级关系 |
相关题目
- LeetCode 102. 二叉树的层序遍历 - 中等
- LeetCode 103. 二叉树的锯齿形层序遍历 - 中等
- LeetCode 199. 二叉树的右视图 - 中等
- LeetCode 429. N叉树的层序遍历 - 中等