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