একটি সমস্যা সমাধানের জন্য যেখানে আমাদের একটি বাইনারি গাছ দেওয়া হয়েছে। এখন আমাদের সর্বাধিক সংখ্যক বাঁক থাকার পথটি খুঁজে বের করতে হবে। যেমন, একটি বাঁক বিবেচনা করা হয় যখন পথের দিক বাম থেকে ডানে বা বিপরীত দিকে পরিবর্তিত হয়, উদাহরণস্বরূপ
ইনপুট -
আউটপুট -
6
এখন এই পদ্ধতিতে, আমরা গাছের মধ্য দিয়ে অতিক্রম করব এবং পূর্ববর্তী গতিবিধির উপর নজর রাখব। যদি দিক পরিবর্তন হয়, আমরা কেবল আমাদের বাঁকের সংখ্যা আপডেট করি এবং তারপরে আমরা সর্বাধিক খুঁজে পাই।
সমাধান খোঁজার পদ্ধতি
এই পদ্ধতিতে, আমরা সমস্ত পথ অতিক্রম করব, এবং আমরা আমাদের উত্তর আপডেট করার সর্বাধিক সংখ্যক বাঁক খুঁজে পাব।
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
struct Node { // structure of our node
int key;
struct Node* left;
struct Node* right;
};
struct Node* newNode(int key){ // initializing our node
struct Node* node = new Node();
node->left = NULL;
node->right = NULL;
node->key = key;
return node;
}
void maximumBends(struct Node* node,char direction, int bends,
int* maxBends, int soFar,int* len){
if (node == NULL) // if null is reached
return;
if (node->left == NULL && node->right == NULL) { // if we reach the leaf node then
//we check if we have to update our answer or not
if (bends > *maxBends) {
*maxBends = bends;
*len = soFar;
}
}
else {
if (direction == 'l') { // current direction is left
maximumBends(node->left, direction,bends, maxBends,soFar + 1, len);
maximumBends(node->right, 'r',bends + 1, maxBends,soFar + 1, len); // if we change direction so bend also increases
}
else {
maximumBends(node->right, direction,bends, maxBends,soFar + 1, len);
maximumBends(node->left, 'l',bends + 1, maxBends,soFar + 1, len); // same as when direction was left
}
}
}
int main(){
struct Node* root = newNode(10);
root->left = newNode(8);
root->right = newNode(2);
root->left->left = newNode(3);
root->left->right = newNode(5);
root->right->left = newNode(2);
root->right->left->right = newNode(1);
root->right->left->right->left = newNode(9);
int len = 0, bends = 0, maxBends = -1;
if(!root) // if tree is empty
cout << "0\n";
else{
if (root->left) // if left subtree exists
maximumBends(root->left, 'l',bends, &maxBends, 1, &len);
if (root->right) // if right subtree exists
maximumBends(root->right, 'r', bends,&maxBends, 1, &len);
cout << len << "\n";
}
return 0;
} আউটপুট
4
উপরের কোডের ব্যাখ্যা
উপরোক্ত পদ্ধতিতে, আমরা কেবলমাত্র সমস্ত পথ অতিক্রম করছি এবং এখন পর্যন্ত পাওয়া বাঁকগুলি গণনা করছি যখন আমরা পথের শেষ প্রান্তে পৌঁছেছি। অর্থাৎ লিফ নোড, আমরা পরীক্ষা করি যে এখান পর্যন্ত বাঁকগুলি আগের সর্বাধিকের চেয়ে বেশি এখন যদি শর্তটি সত্য, তাই আমরা আমাদের সর্বাধিক বাঁক এবং এই নতুন দৈর্ঘ্যের পথের দৈর্ঘ্য আপডেট করি, এবং এভাবেই আমাদের প্রোগ্রাম এগিয়ে যায়।
উপসংহার
এই টিউটোরিয়ালে, আমরা সর্বাধিক সংখ্যক বাঁক বিশিষ্ট পথের দৈর্ঘ্য খুঁজে বের করার জন্য একটি সমস্যার সমাধান করি। আমরা এই সমস্যার জন্য C++ প্রোগ্রাম এবং সম্পূর্ণ পদ্ধতি (স্বাভাবিক) শিখেছি যার মাধ্যমে আমরা এই সমস্যার সমাধান করেছি। আমরা অন্যান্য ভাষা যেমন সি, জাভা, পাইথন এবং অন্যান্য ভাষায় একই প্রোগ্রাম লিখতে পারি। আমরা আশা করি আপনার এই টিউটোরিয়ালটি সহায়ক হবে৷
