C++ में ट्री में सबसे बड़ा उपट्री योग ढूंढें

इस समस्या में, हमें एक बाइनरी ट्री दिया गया है। हमारा कार्य ट्री में सबसे बड़ा उपट्री योग ढूंढना है।

समस्या विवरण: बाइनरी ट्री में धनात्मक और ऋणात्मक दोनों मान होते हैं। और हमें वह उपट्री ढूंढनी है जिसमें नोड्स का अधिकतम योग हो।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

आउटपुट: 13

व्याख्या:

बाएं उपट्री का योग 7 है
दाएं उपट्री का योग 1 है
पूरे ट्री का योग 13 है

समाधान दृष्टिकोण

समस्या को हल करने के लिए, हम पोस्ट-ऑर्डर ट्रैवर्सल करेंगे। बाएं उपट्री और दाएं उपट्री के नोड्स का योग गणना करें। वर्तमान नोड के लिए, जांचें कि क्या वर्तमान नोड के नोड्स का योग बाएं या दाएं उपट्री के योग से बड़ा है। लीफ से रूट तक प्रत्येक नोड के लिए अधिकतम योग ढूंढें।

हमारे समाधान की कार्यप्रणाली को दर्शाने वाला प्रोग्राम,

उदाहरण

#include <iostream>
using namespace std;

struct Node {
    int key;
    Node *left, *right;
};

Node* newNode(int key) {
    Node* temp = new Node;
    temp->key = key;
    temp->left = temp->right = NULL;
    return temp;
}

int calcSumTreeSumRec(Node* root, int& ans) {
    if (root == NULL)
        return 0;
    int currSum = root->key + calcSumTreeSumRec(root->left, ans)+ calcSumTreeSumRec(root->right, ans);
    ans = max(ans, currSum);
    return currSum;
}

int calcMaxSubTreeSum(Node* root) {
    if (root == NULL)
        return 0;
    int ans = -100;
    calcSumTreeSumRec(root, ans);
    return ans;
}

int main() {
    Node* root = newNode(5);
    root->left = newNode(-4);
    root->right = newNode(4);
    root->left->left = newNode(3);
    root->left->right = newNode(8);
    root->right->left = newNode(-5);
    root->right->right = newNode(2);
    cout<<"The largest subtree sum is "<<calcMaxSubTreeSum(root);
    return 0;
}

आउटपुट

The largest subtree sum is 13