记录算法笔记(2025.5.15)二叉树的层序遍历
给你二叉树的根节点 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
思路：
1. 检查根节点是否为空
如果根节点为空，直接返回一个空的二维列表，因为没有节点可以遍历。
2. 初始化队列和结果列表
-
创建一个队列，将根节点加入队列，用于逐层处理节点。
-
创建一个结果列表，用于存储每一层的节点值。
3. 开始层序遍历
使用一个循环，条件是队列不为空。循环体内的操作代表处理一层的节点。
4. 处理当前层的节点
-
获取当前层的节点数量：通过队列的长度确定当前层有多少个节点。
-
创建一个列表存储当前层的节点值：用于临时存储当前层的节点值。
-
逐个处理当前层的节点：
-
从队列中依次取出节点。
-
将节点的值加入当前层的列表。
-
检查当前节点是否有左子节点或右子节点：
-
如果有左子节点，将其加入队列。
-
如果有右子节点，也将其加入队列。
-
-
-
将当前层的节点值列表加入结果列表：完成当前层的处理后，将存储当前层节点值的列表加入最终的结果列表。
5. 重复处理下一层
继续循环，处理下一层的节点，直到队列为空，表示所有层的节点都已处理完毕。
6. 返回结果
最终返回包含所有层节点值的二维列表。
代码：C#
public class Solution {
public IList<IList<int>> LevelOrder(TreeNode root) {
// 如果根节点为空，返回空列表
if (root == null) {
return new List<IList<int>>();
}
// 初始化队列和结果列表
Queue<TreeNode> queue = new Queue<TreeNode>();
queue.Enqueue(root);
IList<IList<int>> ans = new List<IList<int>>();
// 开始层序遍历
while (queue.Count > 0) {
// 获取当前层的节点数量
int len = queue.Count;
// 创建一个列表存储当前层的节点值
List<int> currentLevel = new List<int>();
// 遍历当前层的所有节点
for (int i = 0; i < len; 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);
}
}
// 将当前层的节点值列表加入结果列表
ans.Add(currentLevel);
}
// 返回最终结果
return ans;
}
}