কম্পিউটার

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


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

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

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

  1. C++-এ BST II-তে Inorder Successor

  2. C++ এ উল্টানো সাবট্রি

  3. দুই যোগফল IV - ইনপুট হল C++ এ একটি BST

  4. C++ এ BST কে গ্রেটার ট্রিতে রূপান্তর করুন