C++ এ সবচেয়ে বড় BST সাবট্রি

ধরুন আমাদের একটি বাইনারি গাছ আছে; আমাদের এটির সবচেয়ে বড় সাবট্রি খুঁজে বের করতে হবে যেখানে বৃহত্তম মানে সাবট্রি যার মধ্যে সবচেয়ে বেশি সংখ্যক নোড রয়েছে।

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

তাহলে আউটপুট হবে 3, কারণ সবচেয়ে বড় BST সাবট্রি, এই ক্ষেত্রে, হাইলাইট করা হয়।

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

• ডেটা নামক একটি কাঠামোকে সংজ্ঞায়িত করুন, চারটি মান থাকবে, আকার, maxVal, minVal এবং ঠিক আছে, ঠিক আছে শুধুমাত্র সত্য/মিথ্যা মান ধরে রাখতে পারে

• সমাধান (ট্রিনোড * নোড)

• যদি নোড নাল হয়, তাহলে &miuns;

  • শুরু করে ডেটা ফেরত দিন (0, ইনফিনিটি, -ইনফিনিটি, সত্য)

• বাম :=সমাধান (নোডের বামে)

• বাম :=সমাধান (নোডের ডানদিকে)

• curr

  নামে একটি ডেটা সংজ্ঞায়িত করুন

• curr.ok :=মিথ্যা

• যদি নোডের val>=right.minVal, তাহলে −

  • রিটার্ন curr

• যদি নোডের val <=left.maxVal, তাহলে −

  • রিটার্ন curr

• যদি left.ok সত্য হয় এবং right.ok সত্য হয়, তাহলে −

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

  • curr.ok :=সত্য

  • curr.maxVal :=সর্বাধিক (নোডের ভ্যাল এবং right.maxVal)

  • curr.minVal :=সর্বাধিক (নোডের ভ্যাল এবং left.minVal)

• যদি curr.ok সত্য হয়, তাহলে -

  • ret :=সর্বোচ্চ ret এবং curr.sz

  • রিটার্ন 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;
   Data(){}
   Data(int a, int b, int c, bool d){
      sz = a;
      minVal = b;
      maxVal = c;
      ok = d;
   }
};
class Solution {
public:
   int ret;
   Data solve(TreeNode* node){
      if (!node)
         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.sz = 1 + left.sz + right.sz;
         curr.ok = true;
         curr.maxVal = max(node->val, right.maxVal);
         curr.minVal = min(node->val, left.minVal);
      }
      if (curr.ok)
         ret = max(ret, curr.sz);
      return curr;
   }
   int largestBSTSubtree(TreeNode* root){
      ret = 0;
      solve(root);
      return ret;
   }
};
main(){
   Solution ob;
   vector<int< v = {10,5,15,1,8,NULL,7};
   TreeNode *root= make_tree(v);
   cout << (ob.largestBSTSubtree(root));
}

ইনপুট

[10,5,15,1,8,null,7]

আউটপুট

3