দুটি বাইনারি ট্রি দেওয়া আছে। সেগুলো স্ট্রাকচারলি আইডেন্টিক্যাল এবং নোড মানগুলো সমান কিনা চেক করুন।
উদাহরণ: [1,2,3], [1,2,3] -> true।
সমাধানের ধাপসমূহ
- রিকারসিভ ফাংশন isSameTree(p, q):
- যদি p এবং q দুটোই NULL, true।
- যদি একটিই NULL, false।
- যদি p->val == q->val এবং left ও right সাবট্রি Same Tree হয়, true।
- অন্যথায় false।
C++ কোড উদাহরণ
#include <bits/stdc++.h>
using namespace std;
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) { val = data; left = NULL; 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;
}
class Solution {
public:
bool isSameTree(TreeNode *p, TreeNode* q) {
if (p == NULL && q == NULL) return true;
if (p == NULL || q == NULL) return false;
if (p->val == q->val && isSameTree(p->left, q->left) && isSameTree(p->right, q->right))
return true;
return false;
}
};
int main() {
Solution ob;
vector<int> v = {1,2,3}, v1 = {1,2,3};
TreeNode *root1 = make_tree(v);
TreeNode *root2 = make_tree(v1);
cout << ob.isSameTree(root1, root2);
return 0;
}
ইনপুট
{1,2,3}, {1,2,3}
আউটপুট
1
