# \[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
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blessbingo.gitbook.io/garnet/suan-fa/shu/437-lu-jing-zong-he-iii.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.