C++ में उस ट्री के क्लोन में बाइनरी ट्री के कॉरेस्पॉन्डिंग नोड को ढूंढना

मान लीजिए हमारे पास दो बाइनरी ट्रीज़ original और cloned हैं और original ट्री में एक नोड target का रेफरेंस दिया गया है। क्लोन किया गया ट्री वास्तव में original ट्री की एक कॉपी है। हमें क्लोन किए गए ट्री में उसी नोड का रेफरेंस ढूंढना है।

तो अगर ट्री नीचे जैसा है और टारगेट 3 है, तो आउटपुट 3 होगा।

इसे हल करने के लिए, हम इन स्टेप्स को फॉलो करेंगे:

• solve() नाम का एक मेथड डिफाइन करें, जो node1, node2 और target लेगा

• अगर node1 नल है, तो नल लौटाएं

• अगर node1 target है और node1 का वैल्यू node2 के वैल्यू के बराबर है, तो node2 लौटाएं

• leftPart := solve(node1 का लेफ्ट, node2 का लेफ्ट, target)

• rightPart := solve(node1 का राइट, node2 का राइट, target)

• leftPart लौटाएं अगर leftPart नल नहीं है, अन्यथा rightPart

• मेन मेथड से solve(original, cloned, target) कॉल करके लौटाएं

उदाहरण (C++)

बेहतर समझ के लिए निम्न इम्प्लीमेंटेशन देखें:

#include <bits/stdc++.h>
using namespace std;

class TreeNode{
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data){
        val = data;
        left = 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;
}

class Solution {
public:
    TreeNode* solve(TreeNode* node1, TreeNode* node2, TreeNode* target){
        if(!node1) return NULL;
        if(node1 == target && node1->val == node2->val) return node2;
        TreeNode* leftPart = solve(node1->left, node2->left, target);
        TreeNode* rightPart = solve(node1->right, node2->right, target);
        return leftPart? leftPart : rightPart;
    }
    TreeNode* getTargetCopy(TreeNode* original, TreeNode* cloned, TreeNode* target) {
        return solve(original, cloned, target);
    }
};

int main(){
    vector<int> v = {7,4,3,NULL,NULL,6,19};
    TreeNode *root = make_tree(v);
    TreeNode *cloned = make_tree(v);
    TreeNode *target = root->right; //वैल्यू 3 वाला नोड
    Solution ob;
    cout << (ob.getTargetCopy(root, cloned, target))->val;
}

इनपुट

[7,4,3,null,null,6,19] 3

आउटपुट

3