# 437. Path Sum III
> https://leetcode.com/problems/path-sum-iii/
###### tags: `DFS`

## By Felicia
Runtime: 3 ms, 99.95%
Memory Usage: 36.8 MB, 100%
Lang: Java

Same concept as YuZhen's solution

class Solution {
    public int pathSum(TreeNode root, int sum) {
        Map<Integer, Integer> targetToPaths = new HashMap<>();
        targetToPaths.put(0, 1);
        return findPaths(root, sum, 0, targetToPaths);
    }
    
    private int findPaths(TreeNode root, int target, int sum, Map<Integer, Integer> targetToPaths) {
        if (root == null) {
            return 0;
        }
        
        int currSum = sum + root.val;
        int paths = targetToPaths.getOrDefault(currSum - target, 0);
        targetToPaths.put(currSum, targetToPaths.getOrDefault(currSum, 0) + 1);
        
        paths += findPaths(root.left, target, currSum, targetToPaths) + findPaths(root.right, target, currSum, targetToPaths);
        
        targetToPaths.put(currSum, targetToPaths.get(currSum) - 1);
        
        return paths;
    }
}

## By YuZhen

### DFS: O(n)
Runtime: 4 ms, 100%
Memory: 5 MB, 20%
Lang: Golang

// m is the prefix sum map from root to current node
// key = prefix sum
// value = frequency
// curSum = sum from root to current node
// sum = target sum 
// if m[curSum-sum] > 0, 
// it means there are m[curSum-sum] paths which sums up to sum
func pathSumDFS(node *TreeNode, sum int, m map[int]int, res *int, curSum int) {
    if node == nil { return }
    
    curSum += node.Val
    *res += m[curSum-sum]
    m[curSum]++
    pathSumDFS(node.Left, sum, m, res, curSum)
    pathSumDFS(node.Right, sum, m, res, curSum)
    
    // Golang map is passed by reference, 
    // so curSum has to be back to previous status
    m[curSum]--
}

func pathSum(root *TreeNode, sum int) int {
    res := 0
    pathSumDFS(root, sum, map[int]int{ 0: 1 }, &res, 0)
    return res
}

## By ChungYi
#### Rescursion & DFS
#### performance: 8 ms 40.1 MB 67%

DFS search each node by **pathSumFromRoot** function.
**pathSumFromRoot**: From this point as start point to find the sum.

Extra:
I find out there is a part can be improved. There are overlap computing among pathSumFromRoot.
I will use DP to optimize this part.

class Solution {
    private int res;

    public int pathSum(TreeNode root, int sum) {
        this.res = 0;
        if (root != null)
            DFS(root, sum);
        return res;
    }

    public void DFS(TreeNode root, int sum) {
        this.res += pathSumFromRoot(root, sum);
        if (root.left != null)
            DFS(root.left, sum);
        if (root.right != null)
            DFS(root.right, sum);
    }

    public int pathSumFromRoot(TreeNode root, int sum) {

        if (root.left == null && root.right == null) {
            if (root.val == sum) {
                return 1;
            } else {
                return 0;
            }
        }
        int res = 0;
        if (root.val == sum)
            res += 1;

        if (root.left != null) {
            res += pathSumFromRoot(root.left, sum - root.val);
        }

        if (root.right != null) {
            res += pathSumFromRoot(root.right, sum - root.val);
        }

        return res;
    }

}