/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* struct TreeNode *left;
* struct TreeNode *right;
* };
*/
/**
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *returnColumnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume
* caller calls free().
*/
// 对于返回值是二维数组，一般还需要返回二维数组的行和列的数量，这里returnSize行的个数，returnColumnSizes[]存储着每一行有多少元素
int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes) {
int** arr = (int**)malloc(sizeof(int*) * 2001);//存储结果
*returnColumnSizes =malloc(sizeof(int)* 2001) ; //存储二维数组每行多少元素
*returnSize = 0; //初始化行数
if (root == NULL)
return NULL;
struct TreeNode* queue[2001];// 模拟队列
//初始化队列参数
struct TreeNode* node;
int front, rear;
front = 0;
rear = 0;
queue[rear++] = root;// 根节点入队
while (front < rear) { //队列不为空
int len = rear- front;//每层长度
int* level = malloc(sizeof(int)*len);//定义一个数组，用于存储一层的元素
(*returnColumnSizes) [(*returnSize)] = len;//记录每层长度
for (int i = 0; i < len; i++) { //将这层的所有元素出队，并将这层元素的左右节点依次入队
node = queue[front++];
level[i] = node->val;
if (node->left != NULL)
queue[rear++] = node->left;
if (node->right != NULL)
queue[rear++] = node->right;
}
arr[(*returnSize)++] = level;//将这层元素的值直接赋值给结果数组
}
return arr;
}
