আপনাকে প্রি-অর্ডার ট্রাভার্সালের ফলাফল দেওয়া হয়েছে। আপনাকে মূলের থেকে ছোট উপাদানের সংখ্যা খুঁজে বের করতে হবে।
প্রি-অর্ডার ট্রাভার্সালের প্রথম উপাদানটি হল BST-এর মূল। আসুন একটি উদাহরণ দেখি।
ইনপুট
preorder_result = [5, 4, 2, 1, 7, 6, 8, 9]
আউটপুট
3
মূলের চেয়ে কম তিনটি উপাদান আছে। মূল হল 5।
অ্যালগরিদম
-
একটি অ্যারেতে প্রি-অর্ডার ফলাফল শুরু করুন।
-
একটি ভেরিয়েবলের মধ্যে প্রথম উপাদান অর্থাৎ BST-এর রুট সংরক্ষণ করুন।
-
একটি লুপ লিখুন যা প্রি-অর্ডার ফলাফলের 2য় উপাদান থেকে পুনরাবৃত্তি হয়।
-
রুটের সাথে প্রতিটি উপাদানের তুলনা করুন।
-
যদি বর্তমান উপাদান রুট থেকে বড় হয়, তাহলে গণনা বৃদ্ধি করুন।
-
-
গণনা ফেরত দিন।
বাস্তবায়ন
C++
-এ উপরের অ্যালগরিদমের বাস্তবায়ন নিচে দেওয়া হল#include <bits/stdc++.h>
using namespace std;
int getElementsCount(int arr[], int n) {
if (n < 0) {
return 0;
}
int i, root = arr[0], count = 0;
for(i = 1; i < n; i++) {
if(arr[i] < root) {
count += 1;
}
}
return count;
}
int main() {
int preorder[] = {5, 4, 2, 1, 7, 6, 8, 9};
int n = 8;
cout << getElementsCount(preorder, n) << endl;
return 0;
} আউটপুট
আপনি যদি উপরের কোডটি চালান, তাহলে আপনি নিম্নলিখিত ফলাফল পাবেন।
3
