时间戳

首页 > 解决方案 > leetcode二叉树遍历上的heap-use-after-free

c - leetcode二叉树遍历上的heap-use-after-free

问题描述

它在我的 Xcode 中运行正常，所以任何人都可以告诉我有什么问题吗？

我测试过，问题在于重新分配堆栈空间，但我不明白错误.. 测试用例是 [1,null,2,3] 所以 1 是根，2 是 1 的右孩子，3 是 2 的左孩子. 解决方案应返回数组 [1,2,3]。

 /**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 *
 **
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */

struct TreeNode* cercaRoot(struct TreeNode* root, struct TreeNode** stack, int* stackSize){
    if (root->left){

    *stackSize += 1;
    stack = realloc(stack, (*stackSize)*sizeof(struct TreeNode*));
    stack[*stackSize-1] = root;

    return root->left;

    } else if (root->right){
        return root->right;
    } else{
        while(*stackSize){
            root = stack[*stackSize-1];
            if (root->right) {
                *stackSize -= 1;
                stack = realloc(stack, (*stackSize)*sizeof(struct TreeNode*));

                return root->right;
            } else {
                *stackSize -= 1;
                stack = realloc(stack, (*stackSize)*sizeof(struct TreeNode*));
            }
        }
        return NULL;
    }
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
    *returnSize = 0;
    if (root==NULL) return NULL;

    int* array = calloc(1, sizeof(int));
    array[0]=root->val;
    *returnSize += 1;

    int stackSize = 0;

    struct TreeNode** stack = calloc(1, sizeof(struct TreeNode*));

    root = cercaRoot(root, stack, &stackSize);

    while (root){
        array = realloc(array, (*returnSize+1)*sizeof(int));
        array[*returnSize]=root->val;
        *returnSize+=1;

        root = cercaRoot(root, stack, &stackSize);
    }

    //free(stack);

    return array;

}

标签： cbinary-treerealloc

解决方案

这段代码我没有收到任何错误

输出是：

ret[0] = 1

ret[1] = 2

ret[2] = 3

#include <stdio.h>
#include <stdlib.h>

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



 /*
 **
 * Return an array of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */

struct TreeNode* cercaRoot(struct TreeNode* root, struct TreeNode** stack, int* stackSize){
    if (root->left){

    *stackSize += 1;
   stack = realloc(stack, (*stackSize)*sizeof(struct TreeNode*));
   stack[*stackSize-1] = root;

return root->left;

} else if (root->right){
    return root->right;
} else{
    while(*stackSize){
        root = stack[*stackSize-1];
        if (root->right) {
            *stackSize -= 1;
            stack = realloc(stack, (*stackSize)*sizeof(struct TreeNode*));

            return root->right;
        } else {
            *stackSize -= 1;
            stack = realloc(stack, (*stackSize)*sizeof(struct TreeNode*));
        }
    }
    return NULL;
    }
}

int* preorderTraversal(struct TreeNode* root, int* returnSize) {
*returnSize = 0;
if (root==NULL) return NULL;

int* array = calloc(1, sizeof(int));
array[0]=root->val;
*returnSize += 1;

int stackSize = 0;

struct TreeNode** stack = calloc(1, sizeof(struct TreeNode*));

root = cercaRoot(root, stack, &stackSize);

while (root){
    array = realloc(array, (*returnSize+1)*sizeof(int));
    array[*returnSize]=root->val;
    *returnSize+=1;

    root = cercaRoot(root, stack, &stackSize);
}

free(stack);

return array;

}

struct TreeNode* nodeRoot;

int main(int argc, char** argv) {

int stackSize = 0;
int returnSize = 0;

nodeRoot = malloc(sizeof(nodeRoot));

struct TreeNode* nodeLeft = malloc(sizeof(nodeLeft));
struct TreeNode* nodeRight = malloc(sizeof(nodeRight));

nodeRoot->left = nodeLeft;
nodeRoot->right = nodeRight;

nodeRoot->val = 1;
nodeRoot->left = NULL;
nodeRoot->right->val = 2;
nodeRoot->right->left = malloc(sizeof(nodeLeft));
nodeRoot->right->left->val = 3;

int* ret = preorderTraversal(nodeRoot, &returnSize);

if(ret != NULL){
    for(int i = 0; i < 3; i++){
        printf("ret[i] = %d\n",ret[i]);                   
    }

}

return (EXIT_SUCCESS);
}

如果我在 for 循环中使用 sizeof(ret) 那么我得到：

ret[0] = 1

ret[1] = 2

ret[2] = 3

ret[3] = 0

ret[4] = 0

ret[5] = 0

ret[6] = 33

ret[7] = 0

考虑到分配给数组的有效节点的数量，这是预期的。

无论如何，逻辑似乎很好。我的第一个问题是你如何声明你的测试用例？

推荐阅读