मान लीजिए कि हमारे पास दो बाइनरी पेड़ हैं और विचार करें कि जब हम उनमें से एक को दूसरे को कवर करने के लिए रखते हैं, तो दो पेड़ों के कुछ नोड्स ओवरलैप हो जाते हैं जबकि अन्य ओवरलैपिंग होते हैं। हमें उन्हें एक नए बाइनरी ट्री में मिलाना होगा। मर्ज नियम इस तरह है कि यदि दो नोड्स ओवरलैपिंग कर रहे हैं, तो नोड को मर्ज किए गए नोड के नए मान के रूप में जोड़ दें। अन्यथा, गैर-रिक्त नोड का उपयोग नए पेड़ के नोड के रूप में किया जाएगा।
तो अगर पेड़ हैं -
तब आउटपुट होगा -
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
- विधि हल है ()। यह दो ट्री नोड्स n1 और n2 लेता है। यह इस प्रकार है
- यदि n1 खाली है, और n2 गैर-रिक्त है, तो n2 लौटाएं, अन्यथा जब n2 खाली हो, और n1 खाली न हो, तो n1 लौटाएं, और जब दोनों शून्य हों, तो अशक्त लौटें
- n1 का मान:=n1 का मान + n2 का मान
- n1 के बाएँ:=हल करें (n1 के बाएँ, n2 के बाएँ)
- n1 का दायां:=हल करें (n1 के दाएं, n2 के दाएं)
- वापसी n1
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
#include<bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int v){
val = v;
left = right = NULL;
}
};
void inord(TreeNode *root) {
if (root != NULL) {
inord(root->left);
cout << root->val << " ";
inord(root->right);
}
}
class Solution {
public:
TreeNode* solve(TreeNode* n1, TreeNode* n2) {
if(!n1 && n2)
return n2;
else if(!n2 && n1)
return n1;
else if(!n1 && !n2)
return NULL;
n1->val+=n2->val;
n1->left = solve(n1->left,n2->left);
n1->right = solve(n1->right,n2->right);
return n1;
}
};
main(){
TreeNode *root1 = new TreeNode(1);
root1->left = new TreeNode(3);
root1->right = new TreeNode(2);
root1->left->left = new TreeNode(5);
TreeNode *root2 = new TreeNode(2);
root2->left = new TreeNode(1);
root2->right = new TreeNode(3);
root2->left->right = new TreeNode(4);
root2->right->right = new TreeNode(7);
Solution ob;
TreeNode *root_res = ob.solve(root1, root2);
inord(root_res);
} इनपुट
TreeNode *root1 = new TreeNode(1); root1->left = new TreeNode(3); root1->right = new TreeNode(2); root1->left->left = new TreeNode(5); TreeNode *root2 = new TreeNode(2); root2->left = new TreeNode(1); root2->right = new TreeNode(3); root2->left->right = new TreeNode(4); root2->right->right = new TreeNode(7);
आउटपुट
5 4 4 3 5 7