C++ में बाइनरी ट्री में अधिकतम योग BST

मान लीजिए कि हमारे पास एक बाइनरी ट्री रूट है, हमें किसी भी सबट्री के सभी नोड्स का अधिकतम योग खोजना होगा जो एक बाइनरी सर्च ट्री (BST) भी है।

तो, अगर इनपुट पसंद है,

तो आउटपुट 20 होगा, यह चयनित बीएसटी में सभी नोड्स का योग है।

इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -

• डेटा नामक एक ब्लॉक बनाएं, इसमें sz, maxVal, minVal, ok, sum जैसे कुछ सदस्य होंगे। डेटा के लिए एक इनिशियलाइज़र भी परिभाषित करें, जो इस क्रम में ले जाएगा (sz, minVal, maxVal, ok, और set sum as 0)

• रिट:=0

• हल () नामक एक विधि को परिभाषित करें, यह पेड़ की जड़ लेगा

• यदि नोड शून्य नहीं है या नोड का मान 0 के समान है, तो -

  • एक नया डेटा लौटाएं और इसे (0, inf, -inf, true) द्वारा प्रारंभ करें

• बाएं:=हल करें (नोड के बाएं)

• दाएं =हल करें (नोड के दाएं)

• एक डेटा प्रकार का उदाहरण बनाएं जिसे curr कहा जाता है

• curr.ok :=false

• अगर नोड -> वैल>=right.minVal, तो -

  • वापसी वक्र

• अगर नोड -> वैल <=left.maxVal, तो -

  • वापसी वक्र

• अगर लेफ्ट.ओके नॉन-जीरो है और राइट.ओके नॉन-जीरो है, तो -

  • curr.sum :=वैल + left.sum + right.sum of node

  • रिट :=अधिकतम curr.sum और ret

  • curr.sz :=1 + left.sz + right.sz

  • curr.ok :=सच

  • curr.maxVal :=अधिकतम नोड मान और right.maxVal

  • curr.minVal :=अधिकतम नोड मान और left.minVal

• वापसी वक्र

• मुख्य विधि से निम्न कार्य करें

• रिट:=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}

आउटपुट

20