मान लीजिए हमारे पास एक बाइनरी ट्री है जिसमें प्रत्येक नोड एक पूर्णांक मान रखता है। हमें उन पाथ को ढूंढना है जिनका योग दिए गए मान के बराबर हो। पाथ रूट से लीफ तक होना चाहिए।
समस्या विवरण
यदि ट्री है [5,4,8,11,null,13,4,7,2,null,null,5,1] और योग 22 है, तो परिणाम होगा -

पाथ हैं: [[5,4,11,2],[5,8,4,5]]
एल्गोरिदम
इसे हल करने के लिए हम DFS (डेप्थ-फर्स्ट सर्च) का उपयोग करेंगे जो थोड़ा संशोधित है:
- DFS फंक्शन रूट, शेष योग, और एक अस्थायी ऐरे लेता है
- यदि रूट मौजूद नहीं है, तो लौट जाएं
- यदि रूट का बायां और दायां दोनों खाली हैं (लीफ नोड), तो:
- यदि शेष योग रूट के मान के बराबर है, तो रूट के मान को अस्थायी ऐरे में जोड़ें, अस्थायी ऐरे को परिणाम में जोड़ें, और अंतिम नोड को अस्थायी ऐरे से हटाएं
- रूट के मान को अस्थायी ऐरे में डालें
- बाएं सबट्री के लिए DFS कॉल करें (शेष योग - रूट का मान)
- दाएं सबट्री के लिए DFS कॉल करें (शेष योग - रूट का मान)
- अस्थायी ऐरे से अंतिम तत्व हटाएं (बैकट्रैकिंग)
उदाहरण
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<int> > v) {
cout << "[";
for(int i = 0; i < v.size(); i++) {
cout << "[";
for(int j = 0; j < v[i].size(); j++) {
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]" << endl;
}
class TreeNode {
public:
int val;
TreeNode *left, *right;
TreeNode(int data) {
val = data;
left = 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:
vector<vector<int>> res;
void dfs(TreeNode* root, int sum, vector<int>& temp) {
if(!root) return;
if(!root->left && !root->right) {
if(sum == root->val) {
temp.push_back(root->val);
res.push_back(temp);
temp.pop_back();
}
return;
}
temp.push_back(root->val);
dfs(root->left, sum - root->val, temp);
dfs(root->right, sum - root->val, temp);
temp.pop_back();
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
res.clear();
vector<int> temp;
dfs(root, sum, temp);
return res;
}
};
int main() {
Solution ob;
vector<int> v = {5,4,8,11,NULL,13,4,7,2,NULL,NULL,NULL,NULL,5,1};
TreeNode *root = make_tree(v);
print_vector(ob.pathSum(root, 22));
}
इनपुट
[5,4,8,11,null,13,4,7,2,null,null,5,1] 22
आउटपुट
[[5, 4, 11, 2, ],[5, 8, 4, 5, ],]