讨论/题目交流/#429. N叉树的层序遍历,求助为啥double free了/
#429. N叉树的层序遍历,求助为啥double free了

简介

通过3/37个用例,单用例OK,提交就提示异常。代码没有使用全局变量及静态变量。

最后执行输入:[3,null,1,null,5]
错误提示:

=================================================================
==45==ERROR: AddressSanitizer: attempting double-free on 0x621000003d00 in thread T0:
    #0 0x7f5a713a5c7f in __interceptor_free (/usr/lib/x86_64-linux-gnu/libasan.so.5+0x10bc7f)
    #2 0x7f5a7038a82f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
0x621000003d00 is located 0 bytes inside of 4000-byte region [0x621000003d00,0x621000004ca0)
freed by thread T0 here:
    #0 0x7f5a713a5c7f in __interceptor_free (/usr/lib/x86_64-linux-gnu/libasan.so.5+0x10bc7f)
    #2 0x7f5a7038a82f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
previously allocated by thread T0 here:
    #0 0x7f5a713a6078 in malloc (/usr/lib/x86_64-linux-gnu/libasan.so.5+0x10c078)
    #3 0x7f5a7038a82f in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x2082f)
SUMMARY: AddressSanitizer: double-free (/usr/lib/x86_64-linux-gnu/libasan.so.5+0x10bc7f) in __interceptor_free
==45==ABORTING

代码

代码片段

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     int numChildren;
 *     struct Node** children;
 * };
 */

/**
 * 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().
 */
#define MAX 8000
#define HEIT 1000

int** levelOrder(struct Node* root, int* returnSize, int** returnColumnSizes) {
    struct Node* queue[MAX] = { 0 };
    struct Node* cur = NULL;
    int **res = NULL;
    int *column = NULL;
    int pos, end, tail;
    int i;
    int index = 0;

    *returnSize = 0;
    if (root == NULL) {
        return NULL;
    }

    res = (int**)malloc(HEIT * sizeof(int*));
    memset(res, 0, HEIT * sizeof(int*));

    column = (int*)malloc(HEIT * sizeof(int));
    memset(column, 0, sizeof(int) * HEIT);

    pos = 0;
    queue[0] = root;
    end = 1;
    tail = end;

    res[*returnSize] = (int*)malloc((end - pos) * sizeof(int));
    column[*returnSize] = end - pos;
    *returnSize += 1;

    while (pos != end) {
        cur = queue[pos];
        pos++;

        res[*returnSize - 1][index++] = cur->val;
        i = 0;
        while (i < cur->numChildren) {
            queue[tail++] = cur->children[i];
            i++;
        }

        if (pos == end) {
            end = tail;
            if (end != pos) {
                res[*returnSize] = (int*)malloc((end - pos) * sizeof(int));
                memset(res[*returnSize], 0, (end - pos) * sizeof(int));

                column[*returnSize] = end - pos;
                *returnSize += 1;
                index = 0;
            }
        }
    }

    *returnColumnSizes = column;

    return res;
}
展开讨论
共 1 个讨论

root = NULL 时这样初始化一下 returnColumnSizes 就可以了

if(root == NULL)
{
    *returnSize = 0;
    *returnColumnSizes = malloc(0);
    return NULL;
}
2