C++ এ একটি গাছের মধ্যে সবচেয়ে বড় সাবট্রি সমষ্টি খুঁজুন

এই সমস্যায়, আমরা একটি বাইনারি গাছ দেওয়া হয়. আমাদের কাজ হল একটি গাছের মধ্যে সবচেয়ে বড় সাবট্রি যোগফল খুঁজে বের করা।

সমস্যা বর্ণনা: বাইনারি গাছ ধনাত্মক এবং নেতিবাচক মান নিয়ে গঠিত। এবং আমাদের এমন সাবট্রি খুঁজে বের করতে হবে যেখানে নোডের সর্বোচ্চ যোগফল আছে।

সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক,

আউটপুট: ১৩

ব্যাখ্যা:

বাম-সাবট্রির যোগফল 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