C++ এ বাইনারি সার্চ ট্রিতে প্রি-অর্ডার সিকোয়েন্স যাচাই করুন

ধরুন আমাদের সংখ্যার একটি ক্রম আছে; এটি একটি বাইনারি অনুসন্ধান গাছের সঠিক প্রিঅর্ডার ট্রাভার্সাল সিকোয়েন্স কিনা তা আমাদের পরীক্ষা করতে হবে। আমরা অনুমান করতে পারি যে অনুক্রমের প্রতিটি সংখ্যা অনন্য। নিচের বাইনারি সার্চ ট্রি -

টি বিবেচনা করুন

সুতরাং, যদি ইনপুটটি [5,2,1,3,6] এর মত হয়, তাহলে আউটপুটটি সত্য হবে

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

itr :=-1
কম :=-অসীম
আরম্ভ করার জন্য i :=0, যখন i <প্রি-অর্ডারের আকার, আপডেট (i 1 দ্বারা বাড়ান), করবেন −
- x :=প্রি-অর্ডার[i]
- যদি x <কম হয়, তাহলে −
  - মিথ্যা ফেরত দিন
- যখন (itr>=0 এবং preorder[itr] করুন
  - কম :=প্রি-অর্ডার[itr]
  - (1 দ্বারা এটির হ্রাস করুন)
- (1 দ্বারা itr বাড়ান)
- প্রি-অর্ডার[itr] :=x
প্রত্যাবর্তন সত্য

উদাহরণ

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

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
   bool verifyPreorder(vector<int<& preorder) {
      int itr = -1;
      int low = INT_MIN;
      for (int i = 0; i < preorder.size(); i++) {
         int x = preorder[i];
         if (x < low)
            return false;
         while (itr >= 0 && preorder[itr] < x) {
            low = preorder[itr];
            itr--;
         }
         itr++;
         preorder[itr] = x;
      }
      return true;
   }
};
main(){
   Solution ob;
   vector<int< v = {5,2,1,3,6};
   cout << (ob.verifyPreorder(v));
}

ইনপুট

{5,2,1,3,6}