এই সমস্যায় একটি বাইনারি ট্রি এবং একটি সংখ্যা 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
