ধরুন আমাদের কাছে দুটি বাইনারি ট্রি রয়েছে আসল এবং ক্লোন করা হয়েছে এবং মূল ট্রিতে একটি নোড টার্গেটের রেফারেন্স দেওয়া হয়েছে। ক্লোন করা গাছটি আসলে আসল গাছের কপি। আমাদের ক্লোন করা গাছে একই নোডের একটি রেফারেন্স খুঁজতে হবে।
সুতরাং যদি গাছটি নীচের মত হয় এবং লক্ষ্য 3 হয়, তাহলে আউটপুট 3 হবে।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
সমাধান() নামক একটি পদ্ধতি নির্ধারণ করুন, এটি node1m node2 এবং লক্ষ্য
গ্রহণ করবে -
যদি node1 নাল হয়, তাহলে null ফেরত দিন
-
যদি node1 টার্গেট হয় এবং নোড 1 এর মান হয় node2 এর মান, তাহলে নোড2 ফেরত দিন
-
leftPart :=সমাধান (node1 এর বাম, node2 এর বাম, টার্গেট)
-
rightPart :=সমাধান (নোড 1 এর ডান, নোড 2 এর ডান, লক্ষ্য)
-
leftPart ফেরত দিন, যদি leftPart নাল না হয়, অন্যথায় rightPart
-
মূল পদ্ধতি থেকে কল রিটার্ন সমাধান (অরিজিনাল, ক্লোন, টার্গেট)
উদাহরণ (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);
}
};
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; //The node with value 3
Solution ob;
cout << (ob.getTargetCopy(root, cloned, target))->val;
} ইনপুট
[7,4,3,null,null,6,19] 3
আউটপুট
3
