【重点】【回溯】【前缀和】437. 路径总和 III

题目

法1：前缀和

前缀和+哈希表，最佳解法，牢记！！！
在二叉树上，前缀和相当于从根节点开始的路径元素和。用哈希表dict统计前缀和的出现次数，当我们递归到节点 node 时，设从根到 node 的路径元素和为cur，那么就找到了 dict[cur−targetSum] 个符合要求的路径，加入答案。

问：为什么要把 0 加到哈希表中？

答：这里的 0 相当于前缀和数组中的 s[0]=1。举个最简单的例子，根节点值为 1，targetSum=1。如果不把 0 加到哈希表中，按照我们的算法，没法算出这里有 1 条符合要求的路径。也可以这样理解，要想把任意路径和都表示成两个前缀和的差，必须添加一个 0，否则当路径是前缀时（从根节点开始的路径），没法减去一个数

Python

# 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:
        preSumDict = dict()
        preSumDict[0] = 1

        return self.dfs(root, 0, targetSum, preSumDict)

    def dfs(self, root, cur, targetSum, preSumDict):
        if not root:
            return 0
        res = 0
        cur += root.val           # 遍历到当前节点
        res += preSumDict.get(cur - targetSum, 0)
        oldCount = preSumDict.get(cur, 0)
        preSumDict[cur] = oldCount + 1
        res += self.dfs(root.left, cur, targetSum, preSumDict)
        res += self.dfs(root.right, cur, targetSum, preSumDict)
        preSumDict[cur] = oldCount # 回溯, 恢复现场
        return res

Java

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

    public int dfs(TreeNode root, long cur, int targetSum, Map<Long, Integer> map) {
        int res = 0;
        if (root == null) {
            return 0;
        }
        cur += root.val;
        res += map.getOrDefault(cur - targetSum, 0);
        map.put(cur, map.getOrDefault(cur, 0) + 1);
        res += dfs(root.left, cur, targetSum, map);
        res += dfs(root.right, cur, targetSum, map);
        map.put(cur, map.getOrDefault(cur, 0) - 1); // 回溯

        return res;
    }
}