ধরুন আমাদের দুটি বাইনারি গাছ আছে এবং বিবেচনা করি যে যখন আমরা তাদের একটিকে অন্যটিকে আবৃত করার জন্য রাখি, তখন দুটি গাছের কিছু নোড ওভারল্যাপ হয় যখন অন্যগুলি ওভারল্যাপ হয়। আমাদের তাদের একটি নতুন বাইনারি গাছে একত্রিত করতে হবে। মার্জ নিয়মটি এমন যে যদি দুটি নোড ওভারল্যাপ করা হয়, তাহলে যোগফল নোডের মানগুলি মার্জ করা নোডের নতুন মান হিসাবে বেড়ে যায়। অন্যথায়, অ-খালি নোডটি নতুন গাছের নোড হিসাবে ব্যবহার করা হবে।
তাই যদি গাছ হয় -
তারপর আউটপুট হবে −
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
- পদ্ধতি হল সমাধান()। এটি দুটি ট্রি নোড 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
