मान लीजिए कि हमारे पास एक बाइनरी सर्च ट्री है, अब इस बीएसटी के दो तत्वों की अदला-बदली पर विचार करें, इसलिए हमें इस बाइनरी सर्च ट्री को पुनर्प्राप्त करना होगा।
तो अगर दिया गया पेड़ नीचे जैसा है (पहला वाला), तो बरामद पेड़ होगा (दूसरा वाला) -
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
नोड्स के लिए कुछ पिछला, पहला, दूसरा संदर्भ परिभाषित करें
-
FindProblem () नामक एक विधि को परिभाषित करें, यह नोड लेगा
-
यदि नोड शून्य है, तो वापस लौटें
-
कॉल ढूंढें समस्या (नोड के बाएं)
-
यदि पिछला शून्य नहीं है और पिछला का मान> नोड का मान है, तो
-
अगर पहला शून्य है, तो पहले =पिछला
-
दूसरा:=नोड
-
-
पिछला:=नोड
-
कॉल ढूंढें समस्या (नोड के दाएं)
-
मुख्य विधि से निम्न कार्य करें -
-
इनिशियलाइज़ पिछला, पहला और दूसरा नल के रूप में, कॉल करें findProblem (रूट) और पहले और दूसरे नोड्स के स्वैप मान
उदाहरण (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, ]
