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

题目描述

437. 路径总和 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的升级版. 这里我们考虑的路径不再是从树的根节点到叶子结点, 而是树中任意一部分路径, 不需要从根节点开始, 也不需要尾是根节点.

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

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

# 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