计算节点值的最大总和并计算给出总和的特定路径[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 可能还不够。对于a.sum == b.sum，我简单地采用b。您可能希望根据路径长度来决定，或者始终选择 a 而不是 b。