использование кучи после освобождения при обходе бинарного дерева Leetcode - PullRequest
Новая
       11

использование кучи после освобождения при обходе бинарного дерева Leetcode

0 голосов
/ 13 марта 2019

В моем 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;

}

1 Ответ

0 голосов
/ 13 марта 2019

Я не получаю никакой ошибки с этим кодом

Вывод:

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);
}

Если я использую sizeof (ret) в цикле for, я получаю:

ret [0] = 1

ret [1] = 2

ret [2] = 3

ret [3] = 0

ret [4] =0

ret [5] = 0

ret [6] = 33

ret [7] = 0

Что ожидается, учитываяколичество действительных узлов, назначенных массиву.

Во всяком случае, логика кажется в порядке.Мой первый вопрос: как вы объявляете свой тест?

...