# 437. Path Sum III

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Md5JcnNqnhQfRnxF45c%2F-Md5M3fEOiVkb-cQ2ynO%2Fimage.png?alt=media\&token=1ae3460a-f55e-4a2d-a3fe-95c9f06d05b0)

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Md5JcnNqnhQfRnxF45c%2F-Md5KrirF8c52JMjcy0t%2Fimage.png?alt=media\&token=bcbe3d20-55ab-46a4-8ae4-69929f0c131c)



## DFS  - brute force

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

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-Md5JcnNqnhQfRnxF45c%2F-Md5LTXrXyCllcls_PRR%2Fimage.png?alt=media\&token=59961986-e188-4c92-953f-530ba0bf837c)

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

所以 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 的技巧,&#x20;

以 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);
```

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LekNH5IywF8mjBxFcnu%2F-MdPpKKXmT3Q3bjZWvYT%2F-MdPq8Na2Jljip5jK_7H%2Fimage.png?alt=media\&token=e3b99330-14fe-4947-b7ef-44da3cad03e5)

{% 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);

```

![](https://4272748102-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2F-LekNH5IywF8mjBxFcnu%2Fuploads%2Fv4NcMYlHdkhkJvYLD312%2F%E5%9C%96%E7%89%87.png?alt=media\&token=b34d6e72-e6e9-4226-9582-8c0187a61ebc)

