Lang: C++, Complexity[Time, Space]: [O(height), Recursion Stack Overhead]


#1
void fillPathSum(TreeNode* A,int B,vector<vector<int>> &ans,vector<int> path=vector<int>())
{
    if(A==NULL)
        return;
    else
        path.push_back(A->val);
    
    if(A->left==NULL && A->right==NULL && A->val==B)
        ans.push_back(path);
    else
    {
        fillPathSum(A->left, B-(A->val), ans, path);
        fillPathSum(A->right, B-(A->val), ans, path);
    }
}
vector<vector<int> > Solution::pathSum(TreeNode* A, int B) 
{
    vector<vector<int>> ans;
    fillPathSum(A, B, ans);
    return ans;
}

#2

We can reduce the recursion stack overhead by passing all the variables by reference. I am not sure how significant this change might be, but it’s still an idea. Essentially what I did was something similar. I modified the arguments according to the recursive call and triggered backtracking after the path is explored. I modified the arguments to their original values before triggering backtracking thus allowing me to pass all the variables by reference.