একটি বাইনারি ট্রি দেওয়া আছে যেখানে প্রতিটি নোড একটি পূর্ণসংখ্যা কী ধারণ করে। আমাদের একটি নির্দিষ্ট মানের সমান সমষ্টি वाले পথগুলি খুঁজে বের করতে হবে। পথটি রুট থেকে লিফ পর্যন্ত হতে হবে।
যদি ট্রি হয় [5,4,8,11,null,13,4,7,2,null,null,5,1], এবং সমষ্টি 22 হয়, তবে পথগুলি হবে [[5,4,11,2],[5,8,4,5]]।
সমাধানের পদ্ধতি
- এই সমস্যাটি সমাধানের জন্য একটি ডিএফএস (DFS) ফাংশন ব্যবহার করা হবে, যা কিছুটা সংশোধিত। এই ফাংশনটি রুট, সমষ্টি এবং একটি অস্থায়ী অ্যারে গ্রহণ করবে।
- যদি রুট না থাকে, তবে ফিরে যাওয়া হবে।
- যদি রুটের বাম ও ডান উভয়ই খালি হয় (লিফ নোড), তবে:
- যদি সমষ্টি রুটের মানের সমান হয়, তবে রুটের মান অস্থায়ী অ্যারেতে যোগ করা হবে, অস্থায়ী অ্যারেটি ফলাফলে যোগ করা হবে, এবং তারপর অস্থায়ী অ্যারের শেষ উপাদানটি মুছে ফেলা হবে।
- রুটের মান অস্থায়ী অ্যারেতে যোগ করা হবে।
- বাম সাবট্রির জন্য ডিএফএস কল করা হবে (sum - root->val)।
- ডান সাবট্রির জন্য ডিএফএস কল করা হবে (sum - root->val)।
- অস্থায়ী অ্যারের শেষ উপাদানটি মুছে ফেলা হবে (ব্যাকট্র্যাকিং)।
উদাহরণ
#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));
return 0;
}
ইনপুট
[5,4,8,11,null,13,4,7,2,null,null,5,1] 22
আউটপুট
[[5, 4, 11, 2, ],[5, 8, 4, 5, ],]
