मान लीजिए हमारे पास दो बाइनरी ट्री हैं और जब हम उनमें से एक को दूसरे पर रखते हैं, तो कुछ नोड्स ओवरलैप होते हैं जबकि अन्य नहीं। हमें उन्हें एक नए बाइनरी ट्री में मर्ज करना है। मर्ज नियम यह है कि यदि दो नोड्स ओवरलैप करते हैं, तो उनके मानों को जोड़कर मर्ज किए गए नोड का नया मान बनाया जाता है। अन्यथा, गैर-खाली नोड को नए ट्री के नोड के रूप में उपयोग किया जाता है।
उदाहरण
यदि ट्री निम्नलिखित हैं:
तो आउटपुट होगा:
समाधान दृष्टिकोण
इसे हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:
solve()विधि दो ट्री नोड्सn1औरn2लेती है।- यदि
n1खाली है औरn2गैर-खाली है, तोn2लौटाएं। - यदि
n2खाली है औरn1गैर-खाली है, तोn1लौटाएं। - यदि दोनों खाली हैं, तो
nullलौटाएं। n1का मान :=n1का मान +n2का मान।n1का बायाँ :=solve(n1 का बायाँ, n2 का बायाँ)।n1का दायाँ :=solve(n1 का दायाँ, n2 का दायाँ)।n1लौटाएं।
C++ कार्यान्वयन
#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;
}
};
int 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);
return 0;
}
इनपुट
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
