Given the root of a binary tree and an integer targetSum, return the number of paths where the sum of the values&nbsp;along the path equals&nbsp;targetSum.

The path does not need to start or end at the root or a leaf, but it must go downwards (i.e., traveling only from parent nodes to child nodes).

&nbsp;
Example 1:

Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3
Explanation: The paths that sum to 8 are shown.


Example 2:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: 3


&nbsp;
Constraints:


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


class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
        def util(node: TreeNode, sum_array) -> int:
            t = [e - node.val for e in sum_array]
            zeroes = t.count(0)
            if node.left is None and node.right is None:
                return zeroes
            ansl, ansr = 0, 0
            if node.left:
                ansl = util(node.left, t + [targetSum])
            if node.right:
                ansr = util(node.right, t + [targetSum])
            return ansl + ansr + zeroes

        return util(root, [targetSum]) if root is not None else 0
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        HashMap<Long, Integer> hm = new HashMap<>();
        //hm.put(0L,1); ---> can use this to handle initial condition if c_sum == target sum

        int res = solve(hm, root, targetSum, 0);

        return res;
    }

    public int solve(HashMap<Long, Integer> hm, TreeNode node, long tgt, long c_sum) {

        if(node == null)
            return 0;

        c_sum += node.val;

        int res = 0;

        if(c_sum == tgt) //--> either this condition or the above commented condition.
            res++;

        if(hm.containsKey(c_sum-tgt)){
            res += hm.get(c_sum-tgt);
        }

        hm.put(c_sum, hm.getOrDefault(c_sum,0)+1);

        int left = solve(hm, node.left, tgt, c_sum);
        int right = solve(hm, node.right, tgt, c_sum);

        res += (left+right);

        hm.put(c_sum, hm.getOrDefault(c_sum,0)-1); //remove the calculated cumulative sum

        return res;

    }

}
class Solution {
public:
    int ans = 0,t;
    
    void dfs(unordered_map<long long,int> &curr,TreeNode* node,long long sm){
        
        if(!node){
            return;
        }
                
        sm += (long long) node->val;
        ans += curr[sm-t];
        curr[sm]++;
                
        dfs(curr,node->left,sm);
        dfs(curr,node->right,sm);
        
        curr[sm]--;
    }
    int pathSum(TreeNode* root, int targetSum) {
        if(!root){
            return 0;
        }
        
        t = targetSum;
        unordered_map<long long,int> curr;
        curr[0] = 1;
        long long sm = 0;
        
        dfs(curr,root,sm);

        return ans;
    }
};
var pathSum = function(root, targetSum) {
let count = 0;

let hasSum = (node, target) => { //helper function, calculates number of paths having sum equal to target starting from given node
    if(node===null){// base case
        return;
    }
    if(node.val===target){// if at any point path sum meets the requirement
        count++;
    }
    //recursive call
    hasSum(node.left, target-node.val);
    hasSum(node.right, target-node.val);
}

let dfs = (node) => {//dfs on every node and find sum equal to target starting from every node
    if(node===null)
        return;
    dfs(node.left);
    dfs(node.right);
    hasSum(node,targetSum);// find sum of path starting on this point
}

dfs(root);

return count;
};
Path Sum III