इस समस्या में, हमें एक बाइनरी ट्री और एक नंबर 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