Untitled

mail@pastecode.io avatar
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;
    }
};  */