C++ এ বাইনারি ট্রিতে সর্বোচ্চ BST যোগফল

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

সুতরাং, যদি ইনপুট মত হয়,

তাহলে আউটপুট 20 হবে, এটি নির্বাচিত BST-এর সমস্ত নোডের যোগফল।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

ডেটা নামে একটি ব্লক তৈরি করুন, এটি sz, maxVal, minVal, ok, sum এর মতো কিছু সদস্যকে ধরে রাখবে। এছাড়াও ডেটার জন্য একটি সূচনাকারী সংজ্ঞায়িত করুন, যা এই ক্রমানুসারে নেবে (sz, minVal, maxVal, ok, এবং যোগফল 0 হিসাবে সেট করুন)
ret :=0
সমাধান() নামক একটি পদ্ধতির সংজ্ঞা দিন, এটি গাছের মূল গ্রহণ করবে
যদি নোড অ-শূন্য হয় বা নোডের ভ্যাল 0 এর মতো হয়, তাহলে −
- এটি (0, inf, -inf, true)
  দ্বারা আরম্ভ করে একটি নতুন ডেটা ফেরত দিন
বাম :=সমাধান (নোডের বামে)
অধিকার =সমাধান (নোডের ডানদিকে)
curr
নামে একটি ডেটা টাইপ ইনস্ট্যান্স তৈরি করুন
curr.ok :=মিথ্যা
যদি নোড -> val>=right.minVal, তারপর −
- রিটার্ন curr
যদি নোড -> val <=left.maxVal, তারপর −
- রিটার্ন curr
যদি left.ok অ-শূন্য হয় এবং right.ok অ-শূন্য হয়, তাহলে −
- curr.sum :=val + left.sum + right.sum of node
- ret :=curr.sum এবং ret এর সর্বাধিক
- curr.sz :=1 + left.sz + right.sz
- curr.ok :=সত্য
- curr.maxVal :=নোডের সর্বোচ্চ মান এবং right.maxVal
- curr.minVal :=সর্বাধিক নোড মান এবং left.minVal
রিটার্ন curr
মূল পদ্ধতি থেকে নিম্নলিখিতগুলি করুন
ret :=0
সমাধান(রুট)
রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
   public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      }else{
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      }else{
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int> v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   } return root;
}
struct Data{
   int sz;
   int maxVal;
   int minVal;
   bool ok;
   int sum;
   Data(){}
   Data(int a, int b, int c, bool d){
      sz = a;
      minVal = b;
      maxVal = c;
      ok = d;
      sum = 0;
   }
};
class Solution {
   public:
   int ret = 0;
   Data solve(TreeNode* node){
      if (!node || node->val == 0)
      return Data(0, INT_MAX, INT_MIN, true);
      Data left = solve(node->left);
      Data right = solve(node->right);
      Data curr;
      curr.ok = false;
      if (node->val >= right.minVal) {
         return curr;
      }
      if (node->val <= left.maxVal) {
         return curr;
      }
      if (left.ok && right.ok) {
         curr.sum = node->val + left.sum + right.sum;
         ret = max(curr.sum, ret);
         curr.sz = 1 + left.sz + right.sz;
         curr.ok = true;
         curr.maxVal = max(node->val, right.maxVal);
         curr.minVal = min(node->val, left.minVal);
      }
      return curr;
   }
   int maxSumBST(TreeNode* root){
      ret = 0;
      solve(root);
      return ret;
   }
};
main(){
   Solution ob;
   vector<int> v =
   {1,4,3,2,4,2,5,NULL,NULL,NULL,NULL,NULL,NULL,4,6};
   TreeNode *root = make_tree(v);
   cout << (ob.maxSumBST(root));
}

ইনপুট

{1,4,3,2,4,2,5,NULL,NULL,NULL,NULL,NULL,NULL,4,6}