# C++, 12ms Recursion solution and 16ms Loop solution with stack

• ``````class Solution {
public:
void pathSum_core(TreeNode* root,int cursum,vector<vector<int>>& res, vector<int>& curpath)
{
if (root == NULL)
return;
curpath.push_back(root->val);
cursum -= root->val;
if (root->left == NULL&&root->right == NULL&&cursum==0)
res.push_back(curpath);
else
{
pathSum_core(root->left,cursum, res, curpath);
pathSum_core(root->right, cursum, res, curpath);
}
curpath.pop_back();
cursum += root->val;
return;
}
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> res;
vector<int> curpath;
pathSum_core(root, sum,res, curpath);
return res;
}
};``````

• ``````class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> res;
if (root == NULL)
return res;
stack<TreeNode*> s;
vector<int> curpath;
int stacksum = 0;
TreeNode *pcur=root, *plast=NULL;
while (pcur || !s.empty())
{
while (pcur)
{
s.push(pcur);
curpath.push_back(pcur->val);
stacksum += pcur->val;
pcur = pcur->left;
}
pcur = s.top();
if (pcur->left == NULL&&pcur->right == NULL&&sum == stacksum)
res.push_back(curpath);
if (pcur->right&&pcur->right != plast)
pcur = pcur->right;
else
{
stacksum -= pcur->val;
s.pop();
curpath.pop_back();
plast = pcur;
pcur = NULL;
}
}
return res;
}
};``````

• ``````class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int> > res;
vector<int> path;
genPath(res,path,root,sum);
return res;
}

private:
void genPath(vector<vector<int> > &res,vector<int> path,TreeNode* root, int sum){
if(!root) return;
path.push_back(root->val);
if(root->val == sum && !root->left && !root->right){
res.push_back(path);
return;
}
genPath(res,path,root->left,sum-root->val);
genPath(res,path,root->right,sum-root->val);
}
};``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.