এই সমস্যায়, আমাদের একটি বাইনারি ট্রি এবং একটি সংখ্যা K দেওয়া হয়েছে এবং আমাদের গাছের সমস্ত পাথ প্রিন্ট করতে হবে যেগুলির পাথের নোডের যোগফল k সমান।
এখানে, গাছের পথটি গাছের যে কোনও নোড থেকে শুরু হয়ে যে কোনও নোডে শেষ হতে পারে। পথটি সর্বদা রুট নোড থেকে লিফ নোডে নির্দেশিত হওয়া উচিত। গাছের নোডের মান ধনাত্মক, ঋণাত্মক বা শূন্য হতে পারে।
সমস্যাটি বোঝার জন্য একটি উদাহরণ নেওয়া যাক -
K =5
আউটপুট −
1 3 1 3 2 1 4
এই সমস্যাটি সমাধান করার জন্য, আমরা প্রতিটি নোডকে গাছের মূল নোড হিসাবে বিবেচনা করব এবং অস্থায়ী রুট থেকে অন্যান্য নোডের পথ খুঁজে বের করব যেগুলির মানের যোগফল K।
আমরা পথের সমস্ত নোড ভেক্টরে সংরক্ষণ করি এবং k-তে মূল্যায়ন করার জন্য সমষ্টির মান পরীক্ষা করি।
উদাহরণ
অ্যালগরিদম −
বাস্তবায়ন দেখানোর জন্য প্রোগ্রাম#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
Node *left,*right;
Node(int x){
data = x;
left = right = NULL;
}
};
void printPath(const vector<int>& v, int i) {
for (int j=i; j<v.size(); j++)
cout<<v[j]<<"\t";
cout<<"\n";
}
void findKSumPath(Node *root, vector<int>& path, int k) {
if (!root)
return;
path.push_back(root->data);
findKSumPath(root->left, path, k);
findKSumPath(root->right, path, k);
int f = 0;
for (int j=path.size()-1; j>=0; j--){
f += path[j];
if (f == k)
printPath(path, j);
}
path.pop_back();
}
int main() {
Node *root = new Node(1);
root->left = new Node(3);
root->left->left = new Node(1);
root->left->right = new Node(2);
root->right = new Node(4);
root->right->right = new Node(7);
int k = 5;
cout<<"Paths with sum "<<k<<" are :\n";
vector<int> path;
findKSumPath(root, path, k);
return 0;
} আউটপুট
Paths with sum 5 are − 1 3 1 3 2 1 4
