ধরা যাক আমাদের কাছে একটি বাইনারি ট্রি আছে যার একটি রুট নোড রয়েছে এবং এর বাম শিশু এবং ডান শিশু রয়েছে। কাজটি হল গাছের পাতার নোডের মোট যোগফল খুঁজে বের করা যা তার মূল নোডে রেখে দেওয়া হয়।
উদাহরণস্বরূপ
ইনপুট-1:
আউটপুট:
15
ব্যাখ্যা: প্রদত্ত ইনপুট বাইনারি ট্রিতে, সমস্ত বাম পাতার নোডের যোগফল হল 9+4+2 =15। সুতরাং, আউটপুট হল 15।
এই সমস্যা সমাধানের পদ্ধতি
আমাদের একটি বাইনারি ট্রি রয়েছে এবং কাজটি হল সমস্ত লিফ নোডের যোগফল খুঁজে বের করা যা তার পিতামাতার কাছে রেখে দেওয়া হয়েছে৷
এই সমস্যা সমাধানের পুনরাবৃত্তিমূলক পদ্ধতি হল রুট নোডের বাম নোডটি খালি আছে কিনা তা পরীক্ষা করা। যদি এটি খালি থাকে, তাহলে এর বাম নোডের যোগফল গণনা করুন এবং ডান নোডের জন্য পুনরাবৃত্ত যোগফল খুঁজে বের করুন। সুতরাং, প্রতিটি নোডের জন্য, আমরা পুনরাবৃত্তিমূলকভাবে পরীক্ষা করব এবং এর যোগফল খুঁজে বের করব।
- রুট নোড সহ একটি বাইনারি ট্রি নিন এবং এর বাম শিশুর পাশাপাশি ইনপুট হিসাবে ডান চাইল্ড।
- একটি পূর্ণসংখ্যা ফাংশন leftLeafSum(treenode*root) রুট নোডকে ইনপুট হিসাবে নেয় এবং সমস্ত লিফ নোডের সমষ্টি ফেরত দেয় যা তার পিতামাতার কাছে বাকি থাকে।
- যদি রুট নোড খালি বা NULL হয়, তাহলে 'শূন্য' ফেরত দিন অন্যথায় রুট নোডের বাম নোড পরীক্ষা করুন।
- যদি রুট নোডের বাম নোডে কোনো সন্তান না থাকে, তাহলে বারবার ডান নোডের জন্য পরীক্ষা করুন।
- বাম সন্তান এবং ডান সন্তানের জন্য পুনরাবৃত্তভাবে যোগফল ফেরত দিন।
উদাহরণ
#include<bits/stdc++.h>
using namespace std;
struct treenode {
int data;
treenode * left;
treenode * right;
};
struct treenode * createNode(int d) {
struct treenode * root = new treenode;
root -> data = d;
root -> left = NULL;
root -> right = NULL;
return root;
}
int leftLeafSum(treenode * root) {
if (root == NULL) {
return 0;
}
if (root -> left and!root -> left -> left and!root -> left -> right) {
return root -> left -> data + leftLeafSum(root -> right);
}
return leftLeafSum(root -> left) + leftLeafSum(root -> right);
}
int main() {
struct treenode * root = NULL;
root = createNode(4);
root -> left = createNode(2);
root -> right = createNode(2);
root -> left -> right = createNode(7);
root -> left -> left = createNode(5);
root -> right -> left = createNode(5);
root -> right -> right = createNode(7);
int sum = leftLeafSum(root);
cout << sum << endl;
return 0;
} উপরের কোডটি চালানোর ফলে আউটপুট তৈরি হবে,
আউটপুট
10
ব্যাখ্যা: বাম নোডের লিফ নোডগুলি হল 5 এবং 5 যা তাদের পিতামাতার কাছে ছেড়ে দেওয়া হয়, এইভাবে সমস্ত লিফ নোডের যোগফল =10৷
