Very easy solution c++ using unordered map WITH NO STACK OVERHEAD


#1

bool isleaf(TreeNode* A)
{
if(A->left==NULL&&A->right==NULL)
return true;
else
return false;
}
vector<vector> res;
unordered_map<TreeNode *, vector> mp;
void findpath(TreeNode A,int sum)
{
if(A)
{
if(isleaf(A)&&(sum-A->val)==0)
{
res.push_back(mp[A]);
}
if(A->left)
{
vector t=mp[A];
t.push_back(A->left->val);
mp[A->left]=t;
}
if(A->right)
{
vector t=mp[A];
t.push_back(A->right->val);
mp[A->right]=t;
}
findpath(A->left,sum-(A->val));
findpath(A->right,sum-(A->val));
}
else
return ;
}
vector<vector > Solution::pathSum(TreeNode
A, int B) {
res.clear();
mp.clear();
if(!A)
return res;
vector t;
t.push_back(A->val);
mp[A]=t;
findpath(A,B);
return res;
}