> For the complete documentation index, see [llms.txt](https://blessbingo.gitbook.io/garnet/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://blessbingo.gitbook.io/garnet/suan-fa/shu/437-lu-jing-zong-he-iii.md).

# \[437]\[中等]\[DFS]\[前缀和] 路径总和 III

## 题目描述

[437. 路径总和 III](https://leetcode-cn.com/problems/path-sum-iii/)

给定一个二叉树，它的每个结点都存放着一个整数值。

找出路径和等于给定数值的路径总数。

路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

二叉树不超过1000个节点，且节点数值范围是 \[-1000000,1000000] 的整数。

示例：

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

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

返回 3。和等于 8 的路径有:

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

## 解题思路

[\[113\]\[中等\]\[DFS\] 路径总和 II](broken://pages/-MGiWmOx1YCfwGnuSFxN)的升级版. 这里我们考虑的路径不再是从树的根节点到叶子结点, 而是树中任意一部分路径, 不需要从根节点开始, 也不需要尾是根节点.

无论是统计路径的数量还是具体的路径, 都要使用DFS遍历所有的节点. 我们把从根节点到叶子结点称为完整的路径, 现在的结果可能这个完整路径的子路径, 容易想到[\[560\]\[中等\]\[前缀和\]\[哈希\] 和为K的子数组](/garnet/suan-fa/shu-zu/560-he-weikde-zi-shu-zu.md)这道题目, 只是由数组的形式变为了树中路径的形式, 但本质上都是一样的.

因此在DFS的过程中要维护**根节点到当前路径的长度**, 以及**前缀和哈希表**, 记录每个前缀值出现的次数. 在从当前节点回退到上一层节点的时候, 要特别注意这两个变量的**回溯**.

```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: TreeNode, sum: int) -> int:
        res, target = 0, sum

        def dfs(node, suffix_sum, suffix_mapping, path):
            if node is None:
                return

            val = node.val
            suffix_sum += val
            former = suffix_sum - target
            if former in suffix_mapping:
                nonlocal res
                res += suffix_mapping[former]

            suffix_mapping[suffix_sum] = suffix_mapping.get(suffix_sum, 0) + 1
            path.append(val)

            dfs(node.left, suffix_sum, suffix_mapping, path)
            dfs(node.right, suffix_sum, suffix_mapping, path)

            suffix_mapping[suffix_sum] = suffix_mapping[suffix_sum] - 1
            if suffix_mapping[suffix_sum] == 0:
                del suffix_mapping[suffix_sum]
            path.pop()

        dfs(root, 0, {0: 1}, [])
        return res
```