मान लीजिए कि हमारे पास एक बाइनरी ट्री है। हमें सभी डुप्लिकेट सबट्री खोजने होंगे। इसलिए प्रत्येक प्रकार के डुप्लिकेट सबट्री के लिए, हमें उनमें से किसी एक का रूट नोड वापस करना होगा। तो मान लीजिए हमारे पास −
. जैसा एक पेड़ है
डुप्लीकेट सबट्री हैं -
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- एक एरे रेट बनाएं, एक मैप बनाएं एम
- एक पुनरावर्ती विधि हल () को परिभाषित करें। यह इनपुट के रूप में नोड लेगा। यह काम करता है -
- यदि नोड शून्य है, तो -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, ]