题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，给了一个二叉树，求其中子链的数值和为 targetSum 的数目。子链的定义是二叉树中任意父节点到其子节点的节点链。

思路分享

  • 前缀和的思路，可以参考 【Leetcode Daily】303区域和检索-数组不可变

  • 这个题挺有意思的，通过这道题能够积累到有这么一种思路：可以通过类似二叉树的前序遍历，同时用哈希表记录前缀和。遍历的本质就是枚举子链的重点，这样就能清晰地看到每个有目标和值的子链。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
# 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:
        ans = 0
        cnt = defaultdict(int)
        cnt[0] = 1

        def dfs(node: Optional[TreeNode], s: int) -> None:
            if node is None:
                return

            nonlocal ans
            s += node.val
            ans += cnt[s - targetSum]

            cnt[s] += 1
            dfs(node.left, s)
            dfs(node.right, s)

            cnt[s] -= 1

        dfs(root, 0)
        return ans