【二叉树】层序遍历

做题思路：用队列实现层序遍历

1.将根结点入队

2.求出队列中元素长度，出队同层结点，将他们放到一个数组中

3.将同层节点的所有孩子结点入队

int getLength(int front, int rear) {
    return rear - front;
}

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes){
    *returnSize = 0;
    int** ret = NULL;
    if(!root) {
        return ret;
    }

    //模拟队列
    struct TreeNode* queue[1024];
    int front = 0;
    int rear = 0;

    //将根结点入队
    queue[rear++] = root;

    //创立临时一维数组存储出队元素
    int* arr = NULL;
    int* columnSizes = NULL;

    //辅助变量
    int length = 0;
    struct TreeNode* temp;
    int i = 0;
    while(length = getLength(front, rear)) {
        //更新returnColumnSizes大小
        columnSizes = (int*)realloc(columnSizes, (*returnSize + 1) * sizeof(int));
        columnSizes[*returnSize] = length;
        //更新ret大小
        ret = (int**)realloc(ret, (*returnSize + 1) * sizeof(int*));
        //更新arr大小
        arr = (int*)malloc(length * sizeof(int));
        //取出队中所有元素
        for(i = 0; i < length; i++) {
            temp = queue[front++];
            arr[i] = temp->val;
            if(temp->left)
                queue[rear++] = temp->left;
            if(temp->right)
                queue[rear++] = temp->right;
        }
        //将ret的第returnSize位指向arr
        ret[(*returnSize)++] = arr;
    }
    *returnColumnSizes = columnSizes;
    return ret;
}