ধরুন আমাদের একটি বাইনারি ট্রি আছে। আমাদের সমস্ত ডুপ্লিকেট সাবট্রি খুঁজে বের করতে হবে। তাই প্রতিটি ধরনের ডুপ্লিকেট সাবট্রির জন্য, আমাদের যেকোনো একটি রুট নোড ফেরত দিতে হবে। ধরুন আমাদের একটি ট্রি আছে −
ডুপ্লিকেট সাবট্রিগুলি হল −
এটি সমাধান করতে আমরা নিম্নলিখিত ধাপগুলি অনুসরণ করব −
- একটি অ্যারে ret তৈরি করুন, একটি ম্যাপ m তৈরি করুন
- একটি রিকার্সিভ মেথড solve() সংজ্ঞায়িত করুন। এটি node ইনপুট হিসেবে নেবে। এটি নিম্নরূপ কাজ করে −
- যদি node null হয়, তবে -1 ফেরত দিন
- x := node-এর মান স্ট্রিং হিসেবে, তারপর সেটির সাথে “#” সংযুক্ত করুন।
- left := solve(node-এর বাম), right := solve(node-এর ডান)
- x := x সংযুক্ত “#” সংযুক্ত left, সংযুক্ত “#” সংযুক্ত right
- m[x] ১ বৃদ্ধি করুন
- যদি m[x] ২ হয়, তবে node ret-এ যোগ করুন
- x ফেরত দিন
- মূল মেথড থেকে solve(root) কল করুন এবং ret ফেরত দিন
বेहतर বোঝার জন্য নিচের ইমপ্লিমেন্টেশনটি দেখুন −
উদাহরণ
#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, ]
