计算节点值的最大总和并计算给出总和的特定路径[C]

Question

好吧，我在这里有一个有趣的问题。我得到的任务说我应该计算给定树从根到叶的最大总和。在这种情况下，这是14.那么，问题是，我还需要计算该确切路径的长度，并稍微返回它，因为我需要将总和除以该路径长度。它确实听起来很复杂，起初我认为这很容易，但是我不能找到一种方法来通过特定路径对节点进行计数。也许整个功能count()错误地组装，因为它没有留下任何我需要完成的特定任务的空间。如果有更多的问题，请随时写下来，我需要这个答案。谢谢！

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

struct tree{ 
    int i; 
    struct tree *left; 
    struct tree *right; 
}; 
int count(struct tree *root); 
int max(int,int); 
int main() 
{ 
    struct tree *p=NULL, *q=NULL, *r=NULL, *t=NULL; 

    //1 
    p=(struct tree *)malloc(sizeof(struct tree)); 
    if(p==NULL) exit(1); 
    p->i=1; 
    p->left=NULL; 
    p->right=NULL; 

    //2 
    q=(struct tree *)malloc(sizeof(struct tree)); 
    if(q==NULL) exit(1); 
    q->i=2; 
    q->left=NULL; 
    q->right=NULL; 
    p->left=q; 

    //3 
    r=(struct tree *)malloc(sizeof(struct tree)); 
    if(r==NULL) exit(1); 
    r->i=3; 
    r->left=NULL; 
    r->right=NULL; 
    p->right=r; 

    t=q; 

    //4 
    q=(struct tree *)malloc(sizeof(struct tree)); 
    if(q==NULL) exit(1); 
    q->i=4; 
    q->left=NULL; 
    q->right=NULL; 
    t->left=q; 

    //5 
    q=(struct tree *)malloc(sizeof(struct tree)); 
    if(q==NULL) exit(1); 
    q->i=5; 
    q->left=NULL; 
    q->right=NULL; 
    t->right=q; 

    t=q; 

    //6 
    q=(struct tree *)malloc(sizeof(struct tree)); 
    if(q==NULL) exit(1); 
    q->i=6; 
    q->left=NULL; 
    q->right=NULL; 
    t->left=q; 

    //7 
    q=(struct tree *)malloc(sizeof(struct tree)); 
    if(q==NULL) exit(1); 
    q->i=7; 
    q->left=NULL; 
    q->right=NULL; 
    r->right=q; 
    printf("The sum is %d!",count(p)); 
} 
int count(struct tree *root){ 
    if(root->left!=NULL && root->right!=NULL){ 
     return root->i+max(count(root->left),count(root->right)); 
    } 
    else if(root->left==NULL && root->right!=NULL){ 
     return root->i+count(root->right); 
    } 
    else if(root->left!=NULL && root->right==NULL){ 
     return root->i+count(root->left); 
    } 
    else{ 
     return root->i; 
    } 
} 
int max(int a, int b){ 
    if(a>b){ 
     return a; 
    } 
    else{ 
     return b; 
    } 
} 

Answer 1

我不想改变一切，但只是调整你的代码...

typedef struct { 
    int len; 
    int sum; 
} path_t; 

path_t count(struct tree *root) { 
    path_t a = { .len = 0, .sum = 0}; 
    path_t b = { .len = 0, .sum = 0}; 
    path_t ret; 

    if (root == NULL) 
     return a; // empty sub-tree 

    a = count(root->left); 
    b = count(root->right); 

    if (a.sum > b.sum) { 
     ret.sum = a.sum: 
     ret.len = a.len; 
    } else { 
     ret.sum = b.sum: 
     ret.len = b.len; 
    } 
    ret.sum += root->i; 
    ret.len ++; 
    return ret; 
} 

可能需要照顾的一些细节： 初始化的.sum 0可能是不够的，如果树可以持有负数。我只需要b。您可能需要根据路径长度来决定，或者始终选择a而不是b。