答案：二叉树的层序遍历可通过队列实现，核心步骤为：将根节点入队，循环处理队列中的节点（出队并记录值），并将其左右子节点入队，直到队列为空。以下是详细实现及代码解析：
解题思路- 队列初始化：创建队列结构，包含动态数组、队首/队尾指针及最大容量。
- 处理空树：若根节点为空，直接返回空结果。
- 层序遍历：
当前层处理：记录当前队列长度（即当前层节点数），依次出队并保存节点值。
子节点入队：将出队节点的左右子节点（若存在）入队。
更新结果：为下一层分配空间，层数计数器递增。
- 返回结果：最终返回二维数组，包含每层节点值及对应列数。
代码实现（C语言）#include <stdlib.h>#include <stdbool.h>// 定义二叉树节点结构struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right;};// 定义队列结构typedef struct { struct TreeNode queue; int front, rear, maxsize;} Queue;// 初始化队列void init(Queue *q) { q->maxsize = 5000; q->front = q->rear = 0; q->queue = (struct TreeNode )malloc(sizeof(struct TreeNode *) * q->maxsize);}// 入队操作void push(Queue *q, struct TreeNode *t) { if (t && q->rear < q->maxsize) { q->queue[q->rear++] = t; }}// 出队操作struct TreeNode *pull(Queue *q) { if (q->front < q->rear) { return q->queue[q->front++]; } return NULL;}// 判断队列是否为空bool is_empty(Queue *q) { return q->front == q->rear;}// 获取队列当前长度int len(Queue *q) { return q->rear - q->front;}// 层序遍历主函数int levelOrder(struct TreeNode *root, int *returnSize, int returnColumnSizes) { // 分配结果数组和列数数组空间 int result = (int )malloc(sizeof(int *) * 2000); *returnColumnSizes = (int *)malloc(sizeof(int) * 2000); *returnSize = 0; if (!root) return NULL; Queue q; init(&q); push(&q, root); while (!is_empty(&q)) { int levelSize = len(&q); result[*returnSize] = (int *)malloc(sizeof(int) * levelSize); (*returnColumnSizes)[*returnSize] = levelSize; for (int i = 0; i < levelSize; i++) { struct TreeNode *node = pull(&q); result[*returnSize][i] = node->val; push(&q, node->left); push(&q, node->right); } (*returnSize)++; } free(q.queue); // 释放队列内存 return result;}关键点解析- 队列操作：
入队：检查节点非空且队列未满。
出队：返回队首节点并移动指针。
队列长度：通过 rear - front 计算当前层节点数。
- 动态内存管理：
预先分配足够空间（如2000层）避免频繁扩容。
释放队列内存防止泄漏。
- 结果构造：
每层节点数由队列长度决定，动态分配对应数组空间。
returnColumnSizes 记录每层元素个数，供调用者释放内存。
复杂度分析- 时间复杂度：O(N)，每个节点入队出队一次。
- 空间复杂度：O(N)，队列和结果数组存储所有节点。
总结本题通过队列实现层序遍历，核心在于利用队列的先进先出特性分层处理节点。需注意动态内存分配和释放，避免内存泄漏。此方法适用于树的广度优先搜索（BFS）相关问题。
