realloc() 上的运行时错误 |中序遍历
Runtime error on realloc() | inorder traversal
我正在尝试实现一个中序遍历,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;
}
你几乎肯定在你的代码的其他地方有内存损坏——这段代码对我来说看起来不错(好吧,除了不测试来自 realloc() 的 return 是否为 NULL,但这只会导致你丢失数据,而不是得到你看到的错误)。如果你可以 运行 valgrind 在你的程序上,它可能会指出你的问题。
存在多个问题:
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);
}
我正在尝试实现一个中序遍历,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;
}
你几乎肯定在你的代码的其他地方有内存损坏——这段代码对我来说看起来不错(好吧,除了不测试来自 realloc() 的 return 是否为 NULL,但这只会导致你丢失数据,而不是得到你看到的错误)。如果你可以 运行 valgrind 在你的程序上,它可能会指出你的问题。
存在多个问题:
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);
}