437. 路径总和 III

Difficulty
Medium
Tags
二叉树
URL
https://leetcode-cn.com/problems/path-sum-iii/
Star
给定一个二叉树的根节点 root ，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
示例 1：
notion imagenotion image
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。
示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3
提示:
  • 二叉树的节点个数的范围是 [0,1000]
  • 109 <= Node.val <= 109
  • 1000 <= targetSum <= 1000

法 1 dfs + 前缀和

思路
遍历到某个节点时，在hash中查找前缀和为prefix_sum-target 的节点的个数，结果等于这个个数加上左右子树中满足条件的节点个数。
遍历完树上的所有节点。
题解
# 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, targetSum: int) -> int:
        if root is None:
            return 0
        hashmap = collections.defaultdict(int)
        hashmap[0] = 1
        return self.dfs(root, 0, targetSum, hashmap)

    def dfs(self, root, path_sum, targetSum, hashmap):
        if root is None:
            return 0
        
        path_sum += root.val
        count = hashmap[path_sum-targetSum]
        # 这一步是要在 上一步 之后的
				hashmap[path_sum] += 1

        count += self.dfs(root.left, path_sum, targetSum, hashmap) + \
                self.dfs(root.right, path_sum, targetSum, hashmap)
				# 为什么要移除这个？
				# 为了保证找到的点都是在从上到下的路径上，所以return当前节点之后要撤销
        hashmap[path_sum] -= 1

        return count

# 或者 
# 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:
        self.hash = collections.defaultdict(int)
        self.hash[0] += 1
        path_sum = 0
        self.res = 0

        self.helper(root, targetSum, path_sum=path_sum)
        return self.res

    def helper(self, root, target, path_sum):
        if root is None:
            return
        path_sum += root.val
        self.res += self.hash[path_sum - target]
        self.hash[path_sum] += 1

        self.helper(root.left, target, path_sum)
        self.helper(root.right, target, path_sum)

        self.hash[path_sum] -= 1

法 2 路径保存 + 前缀和

思路
先保存所有从根节点到叶子节点的路径，然后计算各路径上的 结果，最后再累加起来。
这种方法是行不通的。。
因为靠近根节点的部分会多次累加
题解