recursion - 返回最大值的树

Question

                        50
                       /  \
                      30  70 (( which should return 50+70=120 ))
int MyFunction(struct node *root){
    struct node *ptr=root;
    int leftsum=0;
    int rightsum=0;
    if(ptr==NULL){
        return;
    }
    else{

    MyFunction(ptr->left);
     leftsum=leftsum+ptr->key;
    MyFunctipn(ptr->right);
     rightsum=rightsum+ptr->key;
    return (root->key+max(leftsum,rightsum));
    } 
}

为此，我编写了这段代码。也许这是错误的，所以请帮助我，因为我是这个领域的新手。 我想写一个递归代码，它比较两个叶节点(左和右)并将最大值返回给父节点 .

Answer 1

递归函数应如下所示:

int getMaxPath(Node* root){
    // base case, We traveled beyond a leaf
    if(root == NULL){
        // 0 doesn't contribute anything to our answer
        return 0;
    }

    // get the max current nodes left and right children
    int lsum = getMaxPath(root->left);
    int rsum = getMaxPath(root->right);

    // return sum of current node value and the maximum from two paths starting with its two child nodes
    return root->value + std::max(lsum,rsum);

}

完整代码:

#include <iostream>

struct Node{
    int value;
    Node* left;
    Node* right;

    Node(int val){
        value = val;
        left = NULL;
        right = NULL;
    }
};

// make a tree and return a pointer to it's root
Node* buildTree1(){
    /* Build tree like this:
            50
           /  \
          30  70
    */

    Node* root= new Node(50);
    root->left = new Node(30);
    root->right = new Node(70);
}

int getMaxPath(Node* root){
    if(root == NULL){
        // 0 doesn't contribute anything to our answer
        return 0;
    }

    int lsum = getMaxPath(root->left);
    int rsum = getMaxPath(root->right);

    return root->value + std::max(lsum,rsum);

}

int main() {
    using namespace std;

    Node* root = buildTree1();

    int ans = getMaxPath(root);

    cout<< ans <<endl;
    return 0;
}