सी ++ में एक पेड़ में सबसे बड़ा सबट्री योग खोजें

इस समस्या में हमें एक बाइनरी ट्री दिया जाता है। हमारा काम पेड़ में सबसे बड़ा सबट्री योग खोजना है।

समस्या का विवरण: बाइनरी ट्री में सकारात्मक और साथ ही नकारात्मक मान होते हैं। और हमें उस सबट्री को खोजने की जरूरत है जिसमें नोड्स की अधिकतम राशि हो।

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

<मजबूत>

आउटपुट: 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&amp; 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