##### Welcome to Subscribe On Youtube
• import java.util.HashMap;

/**
437	Path Sum III

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

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

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

10
/  \
5   -3
/ \    \
3   2   11
/ \   \
3  -2   1

Return 3. The paths that sum to 8 are:

1.  5 -> 3
2.  5 -> 2 -> 1
3. -3 -> 11

@tag-tree
*/

public class Path_Sum_III {
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/

class Solution {

public int pathSum(TreeNode root, int sum) {
// 路径之和 => 其个数
HashMap<Integer, Integer> preSum = new HashMap<>();

// @note: initialiated to be 1, 当 curSum 等于 sum 的时候，表明从根结点到当前结点正好是一条符合要求的路径
preSum.put(0,1);

return helper(root, 0, sum, preSum);
}

public int helper(TreeNode root, int currSum, int target, HashMap<Integer, Integer> preSum) {
if (root == null) {
return 0;
}

currSum += root.val;
int res = preSum.getOrDefault(currSum - target, 0);

// add before pass down as prevSum
preSum.put(currSum, preSum.getOrDefault(currSum, 0) + 1);

res += helper(root.left, currSum, target, preSum) + helper(root.right, currSum, target, preSum);

// restore, since it's not prevSum when returning to upper recursion
preSum.put(currSum, preSum.get(currSum) - 1);

return res;
}
}
}

############

/**
* 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 {
private Map<Long, Integer> cnt = new HashMap<>();
private int targetSum;

public int pathSum(TreeNode root, int targetSum) {
cnt.put(0L, 1);
this.targetSum = targetSum;
return dfs(root, 0);
}

private int dfs(TreeNode node, long s) {
if (node == null) {
return 0;
}
s += node.val;
int ans = cnt.getOrDefault(s - targetSum, 0);
cnt.merge(s, 1, Integer::sum);
ans += dfs(node.left, s);
ans += dfs(node.right, s);
cnt.merge(s, -1, Integer::sum);
return ans;
}
}

• // OJ: https://leetcode.com/problems/path-sum-iii/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
int ans = 0;
unordered_map<int, int> dfs(TreeNode *root, int sum) { // map of sums from the current node to a child node
if (!root) return {};
unordered_map<int, int> m{ {root->val, 1} };
auto left = dfs(root->left, sum), right = dfs(root->right, sum);
for (auto &[val, cnt] : left) m[val + root->val] += cnt;
for (auto &[val, cnt] : right) m[val + root->val] += cnt;
if (m.count(sum)) ans += m[sum];
return m;
}
public:
int pathSum(TreeNode* root, int sum) {
dfs(root, sum);
return ans;
}
};

• # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
def dfs(node, s):
if node is None:
return 0
s += node.val
ans = cnt[s - targetSum]
cnt[s] += 1
ans += dfs(node.left, s)
ans += dfs(node.right, s)
cnt[s] -= 1
return ans

cnt = Counter({0: 1})
return dfs(root, 0)

############

class Solution(object):
def pathSum(self, root, target):
"""
:type root: TreeNode
:type target: int
:rtype: int
"""
self.count = 0
preDict = {0: 1}

def dfs(p, target, pathSum, preDict):
if p:
pathSum += p.val
self.count += preDict.get(pathSum - target, 0)
preDict[pathSum] = preDict.get(pathSum, 0) + 1
dfs(p.left, target, pathSum, preDict)
dfs(p.right, target, pathSum, preDict)
preDict[pathSum] -= 1

dfs(root, target, 0, preDict)
return self.count


• /**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func pathSum(root *TreeNode, targetSum int) int {
cnt := map[int]int{0: 1}
var dfs func(*TreeNode, int) int
dfs = func(node *TreeNode, s int) int {
if node == nil {
return 0
}
s += node.Val
ans := cnt[s-targetSum]
cnt[s]++
ans += dfs(node.Left, s) + dfs(node.Right, s)
cnt[s]--
return ans
}
return dfs(root, 0)
}

• /**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int pathSum(TreeNode root, int sum) {
if (root == null)
return 0;
return paths(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}

private int paths(TreeNode root, int sum) {
if (root == null)
return 0;
int paths = 0;
if (root.val == sum)
paths++;
paths += paths(root.left, sum - root.val);
paths += paths(root.right, sum - root.val);
return paths;
}
}

############

/**
* 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 {
private Map<Long, Integer> cnt = new HashMap<>();
private int targetSum;

public int pathSum(TreeNode root, int targetSum) {
cnt.put(0L, 1);
this.targetSum = targetSum;
return dfs(root, 0);
}

private int dfs(TreeNode node, long s) {
if (node == null) {
return 0;
}
s += node.val;
int ans = cnt.getOrDefault(s - targetSum, 0);
cnt.merge(s, 1, Integer::sum);
ans += dfs(node.left, s);
ans += dfs(node.right, s);
cnt.merge(s, -1, Integer::sum);
return ans;
}
}

• // OJ: https://leetcode.com/problems/path-sum-iii/
// Time: O(N^2)
// Space: O(N^2)
class Solution {
int ans = 0;
unordered_map<int, int> dfs(TreeNode *root, int sum) { // map of sums from the current node to a child node
if (!root) return {};
unordered_map<int, int> m{ {root->val, 1} };
auto left = dfs(root->left, sum), right = dfs(root->right, sum);
for (auto &[val, cnt] : left) m[val + root->val] += cnt;
for (auto &[val, cnt] : right) m[val + root->val] += cnt;
if (m.count(sum)) ans += m[sum];
return m;
}
public:
int pathSum(TreeNode* root, int sum) {
dfs(root, sum);
return ans;
}
};

• # Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
def dfs(node, s):
if node is None:
return 0
s += node.val
ans = cnt[s - targetSum]
cnt[s] += 1
ans += dfs(node.left, s)
ans += dfs(node.right, s)
cnt[s] -= 1
return ans

cnt = Counter({0: 1})
return dfs(root, 0)

############

class Solution(object):
def pathSum(self, root, target):
"""
:type root: TreeNode
:type target: int
:rtype: int
"""
self.count = 0
preDict = {0: 1}

def dfs(p, target, pathSum, preDict):
if p:
pathSum += p.val
self.count += preDict.get(pathSum - target, 0)
preDict[pathSum] = preDict.get(pathSum, 0) + 1
dfs(p.left, target, pathSum, preDict)
dfs(p.right, target, pathSum, preDict)
preDict[pathSum] -= 1

dfs(root, target, 0, preDict)
return self.count


• /**
* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func pathSum(root *TreeNode, targetSum int) int {
cnt := map[int]int{0: 1}
var dfs func(*TreeNode, int) int
dfs = func(node *TreeNode, s int) int {
if node == nil {
return 0
}
s += node.Val
ans := cnt[s-targetSum]
cnt[s]++
ans += dfs(node.Left, s) + dfs(node.Right, s)
cnt[s]--
return ans
}
return dfs(root, 0)
}