# 437. Path Sum III

![](/files/-Md5M3fEOiVkb-cQ2ynO)

![](/files/-Md5KrirF8c52JMjcy0t)

## DFS  - brute force

把所有子樹都計算一次,  所以跑 以根為起點的樹 ＋ 以左子樹根為起點的樹 ＋ 以右子樹根為起點的樹

![](/files/-Md5LTXrXyCllcls_PRR)

因為這樣就變成嵌套的走訪

所以 time : 最差 O(n^2), BST: O(nlogn)

space: O(n)

```java
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        // DFS all the sub trees, and cal them all
        if (root == null) return 0;
        
        // 注意, 第一個 root 去叫 helper, 另兩個是嵌套, 又呼叫了本身
        // 所以會不斷地嵌套... 
        return helper(root, targetSum) + 
            pathSum(root.left, targetSum) + 
            pathSum(root.right, targetSum); 
    }
    
     private int helper(TreeNode node, int sum) {
        if (node == null) return 0;
         // 不用root to leaf, 所以不用 root.left == null && root.right == null 的條件
        return (node.val == sum ? 1 : 0) 
            + helper(node.left, sum - node.val) + helper(node.right, sum - node.val);
    }
}

```

```java
class Solution {
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) {
            return 0;
        }
        return dfs(root, targetSum) + 
            pathSum(root.left, targetSum) + 
            pathSum(root.right, targetSum);
    }
    private int dfs(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        int leftCount = dfs(root.left, sum - root.val);
        int rightCount = dfs(root.right, sum - root.val);
        return (sum == root.val ? 1 : 0) + leftCount + rightCount;
    }
}
```

## 2. HashMap(presum, path count) + backtracking

如何不走訪所有的 subtree?

use memories 的技巧, 

以 10, 5, 3 這例子, 走訪時計算 presum & path count

(10,1), (15,1), 18 走到 18

(18 - target(8)) = 10 exists in map , 代表有路徑符合我們的 targetSum

so path count = map.get(10)'; map's count record how many path sum count we have

then recursive do node.left & node.right

所以就假設以目前的 sum, 去走左右, 所以先 map  sum,  count+1

```
map.put(sum, map.getOrDefault(sum, 0)+1);

dfs(root.left, targetSum, map, sum);
dfs(root.right, targetSum, map, sum);
```

最後在  backtracking 回來

at last, need to do a backtracking, remove the last   count

```java
map.put(curSum, map.get(curSum) - 1);
```

![](/files/-MdPq8Na2Jljip5jK_7H)

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

idea like subarray sum equals k, just this one is tree style

time: O(n)

space: O(n)

```java
class Solution {
    // use hash map to store map(presum, count)
    // presum, if map.get(presum - target) exists, retirive the count(it's the correct path)
    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, 1); // zero sum, 也是一個 count, 起點, 要注意, 不然有些。case 會有問題 
        return helper(root, 0, targetSum, map);
    }
    private int helper(TreeNode node, int curSum, int targetSum, Map<Integer, Integer> map) {
        if (node == null) return 0;

        curSum += node.val;
        int count = map.getOrDefault(curSum - targetSum, 0);
        
        map.put(curSum, map.getOrDefault(curSum, 0) + 1); // try backtracking
        
        count += helper(node.left, curSum, targetSum, map);
        count += helper(node.right, curSum, targetSum, map);
        
        map.put(curSum, map.get(curSum) - 1); // do backtracking
        return count;
    }
}
```

## global variable

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

    private void dfs(TreeNode root, int targetSum, Map<Integer, Integer> map, int sum) {
        if (root == null) {
            return;
        }
        sum += root.val; // but why use same sum work? becase dfs will go back to upper level
        count += map.getOrDefault(sum - targetSum, 0);
        
        map.put(sum, map.getOrDefault(sum, 0)+1);
        
        dfs(root.left, targetSum, map, sum);
        dfs(root.right, targetSum, map, sum);
        
        map.put(sum, map.get(sum) -1); // notice map backtracking
    }
}

/*

find num of path sum equal to targetSum

map(sum, count)

ex:
Input: root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
Output: 3

map(10, 1)
18 - 8 find in map => count += map(10, 1)

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

       5,
   4,      8,
 11,null,        13,4,
7,2, null,null, 5,1


0,1
5,1

5 4 11 2 = 22 find in (0,1)

27 -22 = 5 find in (5,1)
27 -22 = 5 find in (5,1)

*/
```

#### dfs sum can show all the sum in a tree

```java
private void dfs(TreeNode root, int targetSum, Map<Integer, Integer> map, int sum) {
        if (root == null) {
            return;
        }
        sum += root.val; // but why use same sum work? becase dfs will go back to upper level
        System.out.println(sum);

```

![](/files/DWASHNy8PVpB6qAhNYNS)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://timmybeeflin.gitbook.io/cracking-leetcode/tree/437.-path-sum-iii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.