437. 路径总和 III

根结点到叶子结点的路径上值的和 ：在叶子结点上判断。

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root:return False
        if not root.left and not root.right: # 叶子结点
            return root.val == targetSum
        # 问题转化为左右子树递归
        return self.hasPathSum(root.right, targetSum - root.val) or self.hasPathSum(root.left, targetSum - root.val) 

class Solution:
    def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        if not root: return False
        q = deque([(root, root.val)]) # 通过元组携带前缀和
        # q = [(root, root.val)] # DFS
        while q:
            cur, tem = q.popleft()
            # cur, tem = q.pop()
            if not cur.left and not cur.right: # 叶子结点
                if tem == targetSum: return True
                continue
                
            cur.left and q.append((cur.left, cur.left.val + tem))  
            cur.right and q.append((cur.right, cur.right.val + tem))      
        
        return False

cclaclass Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        
        def dfs(cur, tmp):
            path.append(cur.val)
            tmp -= cur.val
            if not tmp and not cur.left and not cur.right:
                res.append(path[:]) # copy
            
            cur.left and dfs(cur.left, tmp)
            cur.right and dfs(cur.right, tmp)
            path.pop()  # 回溯

        if not root: return []
        res, path = [], []
        dfs(root, targetSum)

        return res

class Solution:
    def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
        if not root: return [] 
        res = []
        q = deque([(root, [], targetSum)])  # 结点，路径，路径和 bfs
        # q = [(root, [], targetSum)]  # dfs

        while q:
            cur, path, tmp = q.popleft() # bfs
            # cur, path, tmp = q.pop() # dfs
            # path += [cur.val]
            # path.append(cur.val) # 列表 +=，append 对象不变 ！！！ 
            path = path + [cur.val] # 对象变了，不再需要 copy path 以及回溯
            tmp -= cur.val
            # 如果是叶子节点，同时和为零。
            if not cur.left and not cur.right and not tmp: 
                    res.append(path) # 保存路径

            cur.left and q.append((cur.left, path, tmp))
            cur.right and q.append((cur.right, path, tmp))

        return res

统计以每个结点为「路径开头」的所有合法路径。

# 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:
        
        # def dfs(cur, tmp):
        #     if not cur: return 0            
        #     tmp -= cur.val             
        #     return dfs(cur.left, tmp) + dfs(cur.right, tmp) + (0 if tmp else 1)

        # if not root: return 0
        # return dfs(root, targetSum) + self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum)

        def dfs(cur, tmp): 
            return dfs(cur.left, tmp - cur.val) + dfs(cur.right, tmp - cur.val) + (0 if tmp != cur.val else 1) if cur else 0

        return dfs(root, targetSum) + self.pathSum(root.left, targetSum) + self.pathSum(root.right, targetSum) if root else 0

统计以每个结点为「路径结尾」的所有合法路径，即从根结点到当前结点的唯一路径中找有多少个结点的路径总和为 targetSum。

统计 sum[y] - sum[x] = targetSum 的数量，其中 x 始结点，y 尾结点 ，即 sum[x] = sum[y] - targetSum，统计 x 数量。
为了更快速的找到某个数值在路径中是否出现过，可以使用哈希表记录路径中每个数值出现的次数。
另外，为了处理包含根节点的情况，需要在哈希表中存储一个 (0,1) 的键值对。而且，并不需要一开始就把前缀和树计算出来，可以边遍历边计算，这里使用回溯来处理，因此这个点已经统计过了，防止影响树的其他分支的数量统计。

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        prefix = collections.defaultdict(int) # 记录路径中某个前缀和 : 出现的次数
        prefix[0] = 1 # 根节点前，前缀和为 0

        def dfs(cur, tmp):
            if not cur:  return 0            

            tmp += cur.val # 当前结点的前缀和
            res = prefix[tmp - targetSum] # 相当于找路径的起点，tmp - 起点的前缀和 = targetSum，即 tmp - targetSum 起点的前缀和。
            prefix[tmp] += 1 # 将当前前缀和个数记录下来
            res += dfs(cur.left, tmp) + dfs(cur.right, tmp)
            prefix[tmp] -= 1 # 回溯

            return res

        return dfs(root, 0)

class Solution:
    def pathSum(self, root: TreeNode, targetSum: int) -> int:
        def f(cur, prefix):
            if not cur: return 0
            prefix = [e + cur.val for e in prefix] + [cur.val]
            return prefix.count(targetSum) + f(cur.left, prefix) + f(cur.right, prefix)
            
            # tmp =  tmp + [cur.val]
            # prefix = list(accumulate(tmp[::-1]))
            # return prefix.count(targetSum) + f(cur.left, tmp) + f(cur.right, tmp)

        return f(root, [])