C++ में बाइनरी सर्च ट्री को पुनर्प्राप्त करना

मान लीजिए हमारे पास एक बाइनरी सर्च ट्री (BST) है, अब इस BST के दो तत्वों को आपस में बदल दिया गया है, इसलिए हमें इस बाइनरी सर्च ट्री को पुनर्प्राप्त करना होगा।

यदि दिया गया ट्री पहले जैसा है, तो पुनर्प्राप्त ट्री दूसरे जैसा होगा।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

• नोड्स के लिए prev, first, second रेफरेंस परिभाषित करें।
• findProblem() नामक एक विधि परिभाषित करें, जो नोड लेती है।
• यदि नोड null है, तो वापस लौटें।
• findProblem(नोड का बायां) कॉल करें।
• यदि prev null नहीं है और prev का मान नोड के मान से अधिक है, तो:
  • यदि first null है, तो first = prev
  • second := नोड
• prev := नोड
• findProblem(नोड का दायां) कॉल करें।
• मुख्य विधि से निम्नलिखित करें:
  • 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); 
}

इनपुट

{1,3,NULL,NULL,2}

आउटपुट

[3, 1, null, null, 2, ]