ধরুন আমাদের একটি বাইনারি সার্চ ট্রি আছে, এখন বিবেচনা করুন এই BST এর দুটি উপাদান অদলবদল করা হয়েছে, তাই আমাদের এই বাইনারি সার্চ ট্রি পুনরুদ্ধার করতে হবে।
সুতরাং যদি প্রদত্ত গাছটি নীচের মত হয় (প্রথমটি), পুনরুদ্ধার করা গাছটি হবে (দ্বিতীয়টি) -
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
নোডের জন্য কিছু পূর্ববর্তী, প্রথম, দ্বিতীয় রেফারেন্স সংজ্ঞায়িত করুন
-
FindProblem() নামে একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি নোড গ্রহণ করবে
-
যদি নোড শূন্য হয়, তাহলে ফেরত দিন
-
কল ফাইন্ড প্রবলেম(নোডের বামে)
-
যদি prev নাল না হয় এবং prev> নোডের মান, তাহলে
-
যদি প্রথমটি শূন্য হয়, তাহলে প্রথম =পূর্ববর্তী
-
দ্বিতীয় :=নোড
-
-
পূর্ববর্তী :=নোড
-
কল ফাইন্ড প্রবলেম(নোডের ডানদিকে)
-
প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -
-
প্রারম্ভিক, প্রথম এবং দ্বিতীয়টিকে নাল হিসাবে, কল FindProblem(root) এবং প্রথম এবং দ্বিতীয় নোডের মান অদলবদল করুন
উদাহরণ (C++)
আরো ভালোভাবে বোঝার জন্য নিচের বাস্তবায়নটি দেখি -
#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;
}
void tree_level_trav(TreeNode*root){
if (root == NULL) return;
cout << "[";
queue q;
TreeNode *curr;
q.push(root);
q.push(NULL);
while (q.size() > 1) {
curr = q.front();
q.pop();
if (curr == NULL){
q.push(NULL);
} else {
if(curr->left)
q.push(curr->left);
if(curr->right)
q.push(curr->right);
if(curr == NULL || curr->val == 0){
cout << "null" << ", ";
}else{
cout << curr->val << ", ";
}
}
}
cout << "]"<<endl;
}
class Solution {
public:
TreeNode* prev;
TreeNode* first;
TreeNode* second;
void swapValue(TreeNode* first, TreeNode* second){
int x = first->val;
first->val = second -> val;
second->val = x;
}
void findProblem(TreeNode* node){
if(!node || node->val == 0)return;
findProblem(node->left);
if((prev!=NULL && prev->val != 0) && prev->val> node->val){
if(!first){
first = prev;
}
second = node;
}
prev = node;
findProblem(node->right);
}
void recoverTree(TreeNode* root) {
prev = first = second = NULL;
findProblem(root);
swapValue(first, second);
}
};
main(){
vector<int> v = {1,3,NULL,NULL,2};
TreeNode *root = make_tree(v);
Solution ob;
ob.recoverTree(root);
tree_level_trav(root);
} ইনপুট
{1,3,NULL,NULL,2} আউটপুট
[3, 1, null, null, 2, ]
