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; } }; */