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

C语言

int** levelOrder(struct TreeNode* root, int* returnSize, int** returnColumnSizes ) {

    // write code here

    if(root == NULL)return NULL;

    *returnSize = -1;

    // **returnColumnSizes = 0; //BUG:指向地址0

    int LayerNodeCnt;

    struct TreeNode* node;

    struct TreeNode** st1 = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*100001);

    struct TreeNode** st2 = (struct TreeNode**)malloc(sizeof(struct TreeNode*)*100001);

    int** ret = (int**)malloc(sizeof(int*) * 100001);

    *returnColumnSizes = (int*)malloc(sizeof(int)*100001);

    // int ret[3][3] = {0};

    int st1_i = -1, st2_i = -1, st2_i_Max;

    st1[++st1_i] = root;

    while(st1_i >= 0){

        if(st1[st1_i] !=NULL){

            while(st1_i >= 0){  //将当前层的元素压入st2

                st2[++st2_i] = st1[st1_i--];

            }

            st2_i_Max = st2_i;  //记录当前层的元素个数

            LayerNodeCnt = 0;

            while(st2_i >= 0){  //将当前层的子节点按顺序压入st1

                node = st2[st2_i--];

                LayerNodeCnt++; //当前层元素计数

                if(node->right) {st1[++st1_i] = node->right; }

                if(node->left)  {st1[++st1_i] = node->left;}

            }

            st2_i = st2_i_Max;

            while(st2_i >= 0){      //将使用完的当前层每隔一个元素+NULL压回st1

                st1[++st1_i] = st2[st2_i--];

                st1[++st1_i] = NULL;

            }

            (*returnSize)++;        //更新层数

            (*returnColumnSizes)[*returnSize] = LayerNodeCnt;       //更新当前层数中元素个数

            ret[*returnSize] = (int*)malloc(sizeof(int)*LayerNodeCnt);//为返回数组申请当前层数的元素存储空间

            LayerNodeCnt = 0;   //为了下面弹栈，需要在这里清0

        }else{

            st1_i--;            //弹出NULL

            ret[*returnSize][LayerNodeCnt++] = st1[st1_i--]->val;   //将已使用的当前层数的元素弹出到ret

        }

    }

    free(st1);

    free(st2);

    (*returnSize)++;        //前面为了方便使用数组，计数是从0开始，退出函数需要变为从1开始，故++

    return (int**)ret;  

}