Root to Leaf Paths With Sum

• Time : $O(n)$
• Space : $O(d)$

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
void dfs(TreeNode* A, vector<vector<int>>& res, vector<int>& now, int target, int sum) {
    sum += A->val;
    now.push_back(A->val);
    if(!A->left and !A->right) {
        if(target == sum) res.push_back(now);
    }
    if(A->left) dfs(A->left, res, now, target, sum);
    if(A->right) dfs(A->right, res, now, target, sum);
    now.pop_back();
}
vector<vector<int>> Solution::pathSum(TreeNode* A, int B) {
    vector<vector<int>> res;
    dfs(A,res,vector<int>() = {}, B, 0);
    return res;
}