题解 | #求二叉树的层序遍历#

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 * };
 */
/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param root TreeNode类 
 * @return int整型二维数组
 * @return int* returnSize 返回数组行数
 * @return int** returnColumnSizes 返回数组列数
 */
#include <malloc.h>

// void Inteam(struct TreeNode* data[1000], int* tail, struct TreeNode* node)
// {
//     if (node != NULL)
//     {
//         data[(*tail)] = node;
//         (*tail)++;
//         (*tail) %= 1000;
//     }
// }

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes ) {
    // write code here
    *returnColumnSizes = (int*)malloc(sizeof(int) * 1500);
    if (root == NULL)
    {
        *returnSize = 0;
        *returnColumnSizes[0] = 0;
        return NULL;
    }
    int **arr = (int**)malloc(sizeof(int*) * 1500);//创建二维数组
    for (int i = 0; i < 1500; i++)
    {

        arr[i] = (int*)malloc(sizeof(int) * 800);
      
    }

    //创建一个循环队列
    struct TreeNode* data[1000] = {0};
    int front = 0;
    int tail = 0;

    data[0] = root;
    tail++;
    struct TreeNode* p = NULL;
    int i = 0;//行数
    int j = 0;//列数
    struct TreeNode* head = root;//记录下一层的开始节点的双亲结点


    while(front != tail)
    {
        //出队
        p = data[front++];
        printf("%d\n", p->val);

        front %= 1000;
        //判断是否为该层第一个元素
        if (p == head->left || (head->left == NULL && p == head->right))
        {
            (*returnColumnSizes)[i] = j;
            j = 0;
            i++;
            arr[i][j++] = p->val;
            struct TreeNode* tmp = p;
            int t = 0;
            while(1)    //更新head的值
            {
                if (tmp->left != NULL || tmp->right != NULL)
                {
                    head = tmp;

                    break;
                }
                if ((front+t)%1000 != tail)
                {
                    tmp = data[(front+t)%1000];
                    t++;
                }
                else 
                {
                    break;
                }
            }
        }
        else 
        {
            arr[i][j++] = p->val;
            printf("%d%d", front, tail);
        }

        //入队
        if (p->left != NULL)
        {
            data[tail++] = p->left;
            tail %= 1000;
        }

        if (p->right != NULL)
        {
            data[tail++] = p->right;
            tail %= 1000;
        }

    }
    (*returnColumnSizes)[i] = j;
    *returnSize = i+1;
    return arr;
}