realloc() 上的运行时错误 |中序遍历

Question

我正在尝试实现一个中序遍历，returns 一个具有遍历值的数组。在我的递归方法中，我试图使用 realloc() 函数来修改数组的大小并存储结果。但是，我收到以下错误：

realloc(): invalid next size。

以下是我的代码：

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

void inorder(struct TreeNode *root, int *res, int *returnSize)
{
    if(root == NULL)
        return;

    //if left node present, traverse left
    inorder(root->left,res,returnSize);

    // add node to array
    res[(*returnSize)]=root->val;
    (*returnSize)++;
    int *temp = realloc(res,sizeof(int)*(*returnSize)); 
    res = temp;

    //if right node present, traverse right
    inorder(root->right,res,returnSize);
}

/**
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* inorderTraversal(struct TreeNode* root, int* returnSize) 
{
    //check if root == null
    if(root == NULL)
    {
        return root;
    }

    //malloc result array to return
    int *res = (int *)malloc(sizeof(int)*(*returnSize));

    //start inorder parsing
    inorder(root, res, returnSize);

    return res;
}

Answer 1

你几乎肯定在你的代码的其他地方有内存损坏——这段代码对我来说看起来不错（好吧，除了不测试来自 realloc() 的 return 是否为 NULL，但这只会导致你丢失数据，而不是得到你看到的错误）。如果你可以运行 valgrind 在你的程序上，它可能会指出你的问题。

Answer 2

存在多个问题：

res 的重新分配值不会返回给调用者。您应该将指针传递给 res 而不是它的值或 return 新分配的指针。
returnSize是一个输出变量，你应该把它初始化为1，或者最好是0并在存储节点值之前重新分配数组。
您应该处理潜在的内存分配失败。

这是更正后的版本：

struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
};

int *inorder(struct TreeNode *root, int *res, int *returnSize) {
    if (root != NULL) {
        //traverse the left tree
        res = inorder(root->left, res, returnSize);

        if (returnSize >= 0) {
            // add node to array
            int *temp = realloc(res, sizeof(int) * (*returnSize) + 1); 
            if (temp == NULL) {
                free(res);
                *returnSize = -1;
                res = NULL;
            } else {
                res = temp;
                res[(*returnSize)++] = root->val;

                //traverse the right tree
                res = inorder(root->right, res, returnSize);
            }
        }
    }
    return res;
}

/**
 * Return an array of size *returnSize.
 * Return NULL and *returnSize=0 for an empty tree.
 * Return NULL and *returnSize<0 for memory allocation failure.
 * Note: The returned array is malloced, the caller must call free().
 */
int *inorderTraversal(struct TreeNode *root, int *returnSize) {
    int *res = NULL;

    *returnSize = 0;
    return inorder(root, res, returnSize);
}

realloc() 上的运行时错误 |中序遍历

Runtime error on realloc() | inorder traversal

c

runtime-error

binary-tree

inorder