题解 | #二叉树中和为某一值的路径(三)#

python3 DFS + 哈希表，双O(n)复杂度。

利用哈希表维护：从根出发的路径和 及其 对应的条数。

当前节点，如果是这样的情况：当前累加和temp - 目标和sum 在哈希表出现，则意味着出现了累加和sum，累加和sum的条数就是temp - sum的条数。如果没出现temp - sum，也就没出现sum。当前累加和同理，出现了则+1，没出现作为键写入哈希表，值为1。

（temp - sum + sum = temp，总和temp，temp-sum的条数就是sum的条数，想象一张琴的琴弦（两端都固定在一点上的），一端有多条路径和为temp-sum的路，那么自然也有同样多条路径和为sum的路，到达另一端）

理解了这个哈希表的作用，剩下就好理解了。

class Solution:
    def FindPath(self, root: TreeNode, sum: int) -> int:
        # 哈希表来记录路径和（从根）及对应条数
        # 路径和为0的有1条
        self.mp = dict()
        self.mp[0] = 1
        
        # lastsum为到上一层为止的累加和
        def dfs(root: TreeNode, sum: int, lastsum: int) -> int:
            # 空结点直接返回
            if root is None:
                return 0
            res = 0
            # 到目前结点为止的累加和
            temp = root.val + lastsum
            # 如果该累加和减去sum在哈希表中出现过，相当于减去前面的分支
            if (temp - sum) in self.mp:
                # 加上有的路径数
                res += self.mp[temp - sum]
            # 增加该次路径和
            if temp in self.mp:
                self.mp[temp] += 1
            else:
                self.mp[temp] = 1
            # 进入子结点
            res += dfs(root.left, sum, temp)
            res += dfs(root.right, sum, temp)
            # 回退该路径和，因为别的树枝不会经过这里了
            self.mp[temp] -= 1
            return res

        return dfs(root, sum, 0)