ノード値の最大合計を数え、合計を与える特定のパスを数える[C]

Question

ここで面白い質問があります。私が与えられた課題は、ルートからリーフまでのツリーの最大合計を計算する必要があるということです。この場合、それは14です。問題は、正確なパスの長さを数え、そのパス長との和を分割する必要があるため、やはりそれを返す必要があるということです。地獄が複雑に聞こえるのは間違いないが、最初はとても簡単だと思ったが、特定の経路でノードを数える方法を見つけることができなかった。関数count()全体が誤ってアセンブルされている可能性があります。より多くの質問がある場合はemを書き留めてください、私はこれが答える必要があります。ありがとう！私はあなたのコードを調整しますが、すべてを変更したくない

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

あなたが世話をする必要があるかもしれませんいくつかの詳細： 場合は0に.SUM初期化すると、十分ではないかもしれませんツリーは負の数を保持できます。 a.sum == b.sumについては、単にbとします。パスの長さに基づいて決定するか、bではなく常にaを選択することができます。