> For the complete documentation index, see [llms.txt](https://coding.bea.ai/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://coding.bea.ai/tree/typical-problems-and-solutions/path-sum-iii.md).

# Path sum III

{% embed url="<https://leetcode.com/problems/path-sum-iii/description/>" %}

It's a good example of double DFS in the brute force implementation&#x20;

```java
class Solution {
  public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        return 
        dfs(root, targetSum, 0) 
        + pathSum(root.left, targetSum) 
        + pathSum(root.right, targetSum);
    }

    private int dfs(TreeNode node, int targetSum, long sum) {
        if (node == null) {
            return 0;
        }
        sum += node.val;
        int count = sum == targetSum ? 1 : 0;
        count += dfs(node.left, targetSum, sum);
        count += dfs(node.right, targetSum, sum);
        return count;
    }
}
```

Where we can use pre-sum to change it to one layer DFS, to optimize the algorithm from O(n2) to O(n)

```java
class Solution {
  int count = 0;
  public int pathSum(TreeNode root, int targetSum) {
         Map<Long, Integer> sumCounterMap = new HashMap<>();
        sumCounterMap.put(0L, 1);
        dfs(root, targetSum, 0L, sumCounterMap);
        return count;
    }

    private void dfs(TreeNode node, int targetSum, long curSum, 
        Map<Long, Integer> sumCounterMap) {
        if (node == null) {
            return;
        }
        curSum += node.val;
        if (sumCounterMap.containsKey(curSum-targetSum)) {
            count += sumCounterMap.get(curSum-targetSum);
        }
        sumCounterMap.put(curSum, sumCounterMap.getOrDefault(curSum, 0) + 1);
        dfs(node.left, targetSum, curSum, sumCounterMap);
        dfs(node.right, targetSum, curSum, sumCounterMap);
        sumCounterMap.put(curSum, sumCounterMap.get(curSum) - 1);
    }
}
```