c - 树中递归的重新分配

Question

我正在尝试找到二叉树中叶到根路径的最大总和，如下所示 http://www.geeksforgeeks.org/find-the-maximum-sum-path-in-a-binary-tree/

1) 我无法找到为什么路径没有在 main() 中打印 这是因为函数中的重新分配错误吗？

2)我的免费也是正确的吗？

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

/* A tree node structure */
struct node
{
    int data;
    struct node *left;
    struct node *right;
};

// Returns the maximum sum and prints the nodes on max sum path
int maxsumtoleaf(struct node *node,int** path,int &height)
{
    // base case
    if (node == NULL)
        return 0;
    printf("\n At node %d,",node->data);
    if (node->left==NULL && node->left==NULL) {
        *path=(int*)realloc(*path,sizeof(int));
        *path[0]=node->data;
        height=1;
        printf("\n value is %d,",*path[0]);
        return node->data;
    }
    // find the target leaf and maximum sum
    int rightheight=0,leftheight=0;
    int *path1=NULL,*path2=NULL;
    int left=maxsumtoleaf (node->left,&path1,leftheight);
    int right=maxsumtoleaf (node->right,&path2,rightheight);
    if ( left > right ) {
        printf("\nbefore left is");
        for(int i=0;i<leftheight;i++)
            printf("%d,",path1[i]);
        path1=(int*)realloc(path1,sizeof(int)*(leftheight+1));
        if ( path1 == NULL ) {
            printf("Out of Memory!\n");
            return 0;
        }
        path1[leftheight]=node->data;
        height=leftheight+1;
        printf("\nafter left %d is ",leftheight);
        for(int i=0;i<height;i++)
            printf("%d,",path1[i]);
        path=&path1;
        return left+node->data;
    } else {
        printf("\nbefore right is");
        for(int i=0;i<rightheight;i++)
            printf("%d,",path2[i]);
        path2=(int*)realloc(path2,sizeof(int)*(rightheight+1));
        if ( path2 == NULL ) {
            printf("Out of Memory!\n");
            return 0;
        }
        path2[rightheight]=node->data;
        height=rightheight+1;
        printf("\nafter right is");
        for(int i=0;i<height;i++)
            printf("%d,",path2[i]);
        path=&path2;
        return right+node->data;
    }
    // return maximum sum
}

/* Utility function to create a new Binary Tree node */
struct node* newNode (int data)
{
    struct node *temp = new struct node;
    temp->data = data;
    temp->left = NULL;
    temp->right = NULL;
    return temp;
}

/* Driver function to test above functions */
int main()
{
    struct node *root = NULL;

    /* Constructing tree given in the above figure */
    /* (8<--2->-4)<-10->7 */
    root = newNode(10);
    root->left = newNode(-2);
    root->right = newNode(7);
    root->left->left = newNode(8);
    root->left->right = newNode(-4);
    int sum=0;

    int** path=NULL;
    int height=0;
    sum = maxsumtoleaf(root,path,height);
    printf ("\nSum of the nodes is %d ,len=%d", sum,height);
    printf ("\nPath is ");
    for(int i=0;i<height;i++)
        printf("%d,",*path[i]);
    free(path);

    getchar();
    return 0;
}

输出:

 At node 10,
 At node -2,
 At node 8,
 value is 8,
 At node -4,
 value is -4,
before left is8,
after left 1 is 8,-2,
 At node 7,
 value is 7,
before right is7,
after right is7,10,
Sum of the nodes is 17 ,len=2
Path is ---> Breaks at this point in main()

Answer 1

代码是 C++，通过引用传递参数并使用 new。

为了制作 C，需要进行许多小修复，包括如何传递 C“引用”变量(显式地通过地址)。

如果分配因丢失原始指针而失败，则您没有正确执行 rellloc()。

释放指针后将指针NULL始终是良好的形式。

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

/* A tree node structure */
struct node {
  int data;
  struct node *left;
  struct node *right;
};

// Returns the maximum sum and prints the nodes on max sum path
int maxsumtoleaf(struct node *node, int** path, int *height) {
  // base case
  if (node == NULL)
    return 0;
  printf("\n At node %d,", node->data);
  if (node->left == NULL && node->left == NULL) {
    *path = (int*) realloc(*path, sizeof(int));
    (*path)[0] = node->data;
    *height = 1;
    printf("\n value is %d,", *path[0]);
    return node->data;
  }
  // find the target leaf and maximum sum
  int rightheight = 0, leftheight = 0;
  int *path1 = NULL, *path2 = NULL;
  int left = maxsumtoleaf(node->left, &path1, &leftheight);
  int right = maxsumtoleaf(node->right, &path2, &rightheight);
  if (left > right) {
    printf("\nbefore left is");
    for (int i = 0; i < leftheight; i++)
      printf("%d,", path1[i]);
    path1 = (int*) realloc(path1, sizeof(int) * (leftheight + 1));
    if (path1 == NULL) {
      printf("Out of Memory!\n");
      return 0;
    }
    path1[leftheight] = node->data;
    *height = leftheight + 1;
    printf("\nafter left %d is ", leftheight);
    for (int i = 0; i < *height; i++)
      printf("%d,", path1[i]);
    *path = path1;
    return left + node->data;
  } else {
    printf("\nbefore right is");
    for (int i = 0; i < rightheight; i++)
      printf("%d,", path2[i]);
    path2 = (int*) realloc(path2, sizeof(int) * (rightheight + 1));
    if (path2 == NULL) {
      printf("Out of Memory!\n");
      return 0;
    }
    path2[rightheight] = node->data;
    *height = rightheight + 1;
    printf("\nafter right is");
    for (int i = 0; i < *height; i++)
      printf("%d,", path2[i]);
    *path = path2;
    return right + node->data;
  }
  // return maximum sum
}

/* Utility function to create a new Binary Tree node */
struct node* newNode(int data) {
  struct node *temp = malloc(sizeof *temp); // new struct node;
  temp->data = data;
  temp->left = NULL;
  temp->right = NULL;
  return temp;
}

/* Driver function to test above functions */
int main() {
  struct node *root = NULL;

  /* Constructing tree given in the above figure */
  /* (8<--2->-4)<-10->7 */
  root = newNode(10);
  root->left = newNode(-2);
  root->right = newNode(7);
  root->left->left = newNode(8);
  root->left->right = newNode(-4);
  int sum = 0;

  int* path = NULL;
  int height = 0;
  sum = maxsumtoleaf(root, &path, &height);
  printf("\nSum of the nodes is %d ,len=%d", sum, height);
  printf("\nPath is %p ", path);
  // return 0;
  for (int i = 0; i < height; i++)
    printf("%d,", path[i]);
  free(path);
  path = NULL;

  // getchar();
  return 0;
}

首选realoc()使用

// Somehow these are to be updated (initial to NULL and 0)
some_type *current_ptr;
size_t current_element_count;  // best too use type size_t

size_t new_element_count = some_function(current_size);
void *new_ptr = realloc(current_ptr, new_element_count * sizeof *current_ptr);
if (new_ptr == NULL && new_element_count > 0) {
  Handle_OOM();  // current_ptr is still same & current_element_count elements
  return;
}
current_ptr = new_ptr;
current_element_count = new_element_count;
// continue on the happy path