ধরুন আমাদের একটি বাইনারি গাছ আছে। আমাদের সব ডুপ্লিকেট সাবট্রি খুঁজে বের করতে হবে। তাই প্রতিটি ধরনের ডুপ্লিকেট সাবট্রির জন্য, আমাদেরকে তাদের যেকোনো একটির রুট নোড ফেরত দিতে হবে। তাহলে ধরুন আমাদের −
এর মত একটি গাছ আছে
ডুপ্লিকেট সাবট্রি হল −
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- একটি অ্যারে রেট তৈরি করুন, একটি মানচিত্র তৈরি করুন m
- একটি পুনরাবৃত্ত পদ্ধতি সংজ্ঞায়িত করুন সমাধান()। এটি নোডকে ইনপুট হিসাবে গ্রহণ করবে। এটি − হিসেবে কাজ করে
- নোড যদি শূন্য হয়, তাহলে -1 ফেরত দিন
- x :=স্ট্রিং হিসাবে নোডের মান, তারপর এটির সাথে "#" সংযুক্ত করুন।
- বাম :=সমাধান (নোডের বামে), ডানে :=সমাধান (নোডের ডানদিকে)
- x :=x কনক্যাটেনেট “#” কানকাটেনেট বাম, কনক্যাটেনেট “#” কনক্যাটেনেট ডানে
- m[x] 1 দ্বারা বাড়ান
- যদি m[x] 2 হয়, তাহলে ret এ নোড প্রবেশ করান
- ফেরত x
- মূল পদ্ধতি থেকে কল সল্ভ(রুট) এবং রিটার্ন রিটার্ন
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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;
}
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->val == 0 || curr == NULL){
cout << "null" << ", ";
} else {
cout << curr->val << ", ";
}
}
}
cout << "]"<<endl;
}
class Solution {
public:
vector <TreeNode*> ret;
map <string, int> m;
string solve(TreeNode* node){
if(!node || node->val == 0){
return "-1";
}
string x = to_string(node->val);
x += "#";
string left = solve(node->left);
string right = solve(node->right);
x = x + "#" + left + "#" + right;
m[x]++;
if(m[x] == 2){
ret.push_back(node);
}
return x;
}
vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) {
ret.clear();
m.clear();
solve(root);
return ret;
}
};
main(){
vector<int> v = {1,2,3,4,NULL,2,4,NULL,NULL,NULL,NULL,4};
Solution ob;
TreeNode *root = make_tree(v);
vector<TreeNode*> trees = ob.findDuplicateSubtrees(root);
for(TreeNode *t : trees){
tree_level_trav(t);
}
} ইনপুট
[1,2,3,4,null,2,4,null,null,null,null,4]
আউটপুট
[4, ] [2, 4, ]
