Untitled

unknown
plain_text
25 days ago
1.7 kB
1
Indexable
Never
```
class Solution {  //FASTER
public:
void solve(TreeNode* root,int sum,int &tsum,vector<int>&ans, vector<vector<int>>&res){
if(root==NULL) return;
sum+=root->val;
ans.push_back(root->val);

if(sum==tsum && !root->left && !root->right){
res.push_back(ans);
//return; //this return will cause exit before pop_back of ans
}

solve(root->left,sum,tsum,ans,res);
solve(root->right,sum,tsum,ans,res);
ans.pop_back(); //one 4 isnt popping , THIS BACKTRACKING CAN BE AVOIDED IF WE DONT PASS ANS BY REF
}

vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> res; vector<int> ans; int sum=0;
solve(root,sum,targetSum,ans,res);
return res;
}
};

// no backtracking SOL
/*
class Solution {
public:
void solve(TreeNode* root,int sum,int &tsum,vector<int>ans, vector<vector<int>>&res){
if(root==NULL) return;
sum+=root->val;
ans.push_back(root->val);

if(sum==tsum && !root->left && !root->right){
res.push_back(ans);
return; //this return will cause exit before pop_back of ans
}

solve(root->left,sum,tsum,ans,res);
solve(root->right,sum,tsum,ans,res);
//ans.pop_back(); //one 4 isnt popping , THIS BACKTRACKING CAN BE AVOIDED IF WE DONT PASS ANS BY REF
}

vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> res; vector<int> ans; int sum=0;
solve(root,sum,targetSum,ans,res);
return res;
}
};  */```