ধরুন আমরা একটি বাইনারি ট্রি দিয়েছি যেখানে প্রতিটি নোড একটি পূর্ণসংখ্যা কী ধারণ করে। আমরা একটি প্রদত্ত মানের যোগফল যে পথ খুঁজে বের করতে হবে. পথটি মূল থেকে পাতা পর্যন্ত শুরু করা উচিত। আমাদের সেই পথ খুঁজে বের করতে হবে যেখানে যোগফল একই।
যদি গাছটি হয় [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;
}
};
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, ],]
