Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

&nbsp;
Example 1:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22


Example 2:

Input: root = [1,2,3], targetSum = 5
Output: []


Example 3:

Input: root = [1,2], targetSum = 0
Output: []


&nbsp;
Constraints:


	The number of nodes in the tree is in the range [0, 5000].
	-1000 &lt;= Node.val &lt;= 1000
	-1000 &lt;= targetSum &lt;= 1000


class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        res = []
        def dfs(v, path, pathsum):
            if not v:
                return
            path.append(v.val)
            pathsum += v.val
            if not v.left and not v.right and pathsum == targetSum:
                res.append(path[:])
            dfs(v.left, path, pathsum)
            dfs(v.right, path, pathsum)
            path.pop()
        dfs(root, [], 0)
        return res
class Solution 
{
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) 
    {
        List<List<Integer>> ans = new ArrayList<>();
        pathSum(root, targetSum, new ArrayList<>(), ans);
        return ans;
    }
    
    public void pathSum(TreeNode root, int targetSum, List<Integer> path, List<List<Integer>> ans)
    {
        if(root == null)
            return;
        path.add(root.val);
        if(root.left == null && root.right == null && targetSum == root.val)//leaf node that completes path
        {
            ans.add(new ArrayList(path));// we use new ArrayList because if we don't the originaly List is added which is mutable, if we add a copy that's not mutable.
        }
        else
        {
            pathSum(root.left, targetSum-root.val, path, ans);
            pathSum(root.right, targetSum-root.val, path, ans);
        }
        path.remove(path.size()-1); //removal of redundant nodes
    }
}
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 * int val;
 * TreeNode *left;
 * TreeNode *right;
 * TreeNode() : val(0), left(nullptr), right(nullptr) {}
 * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> v;
    void helper(vector<int>& t, int target, TreeNode* root){
        if(root==NULL){
            return;
        }
        if(root->left==NULL&&root->right==NULL&&target==root->val){
            t.push_back(root->val);
            v.push_back(t);
            t.pop_back();
            return;
        }
        target=target-root->val;
        t.push_back(root->val);
        helper(t,target,root->left);
        helper(t,target,root->right);
        t.pop_back();

        //cout<<root->val<<" "<<target<<endl;
        return;
    }
    vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
        vector<int> t;
        helper(t,targetSum,root);
        return v;
    }
};
var pathSum = function(root, targetSum) {
  const paths = [];

  function dfs(root, sum, curr = []) {
    if (!root) return;

    const newCurr = [...curr, root.val];
    if (!root.left && !root.right && sum === root.val) return paths.push(newCurr);

    dfs(root.left, sum - root.val, newCurr);
    dfs(root.right, sum - root.val, newCurr);
  }

  dfs(root, targetSum);
  return paths;
};
Path Sum II