ধরুন আমাদের কাছে একটি বাইনারি সার্চ ট্রি (BST) আছে, যাতে দুটি নোডের মান বদলিয়ে দেওয়া হয়েছে। আমাদের কাজ হল এই BST কে পুনরুদ্ধার করা।
যদি দেওয়া ট্রি নিচের প্রথম ছবির মতো হয়, তবে রিকভার করার পর দ্বিতীয় ছবির মতো হবে।
সমাধানের ধাপগুলো:
prev, first, second নামে তিনটি নোড রেফারেন্স সংজ্ঞায়িত করুন।
findProblem() নামে একটি মেথড তৈরি করুন যা একটি নোড গ্রহণ করবে।
যদি নোড null হয়, তবে রিটার্ন করুন।
findProblem(node->left) কল করুন।
যদি prev null না হয় এবং prev->val > node->val হয়, তবে:
যদি first null হয়, তবে first = prev
second = node
prev = node সেট করুন।
findProblem(node->right) কল করুন।
মূল ফাংশন থেকে prev, first, second কে null দিয়ে ইনিশিয়ালাইজ করুন, findProblem(root) কল করুন এবং first ও second নোডের মান বদলিয়ে দিন।
উদাহরণ (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<TreeNode*> 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);
}
};
int main() {
vector<int> v = {1, 3, NULL, NULL, 2};
TreeNode *root = make_tree(v);
Solution ob;
ob.recoverTree(root);
tree_level_trav(root);
return 0;
}
ইনপুট
{1,3,NULL,NULL,2}
আউটপুট
[3, 1, null, null, 2, ]
