realloc() traversal遍历的运行时错误

Question

我正在尝试实现一个无序遍历，该遍历返回带有遍历值的数组。在我的递归方法中，我尝试使用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

有许多问题：

• res的重新分配值不会传递回调用方。您应该将指针传递给res而不是它的值，或者返回新分配的指针。
• 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);
}

Answer 2

您几乎肯定在代码的其他地方有内存损坏--在我看来，这段代码看起来很好(嗯，除了没有测试realloc()返回的空值之外，这只会导致您丢失数据，而不会得到您正在看到的错误)。如果你能在你的程序上运行精力充沛的程序，它可能会给你指出问题。