面试题 04.12. 求和路径

• 标签：树、深度优先搜索、二叉树
• 难度：中等

题目链接

• 面试题 04.12. 求和路径 - 力扣

题目大意

给定一个二叉树的根节点 root，和一个整数 targetSum。

要求：求出该二叉树里节点值之和等于 targetSum 的路径的数目。

• 路径：不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

解题思路

直观想法是：

以每一个节点 node 为起始节点，向下检测延伸的路径。递归遍历每一个节点所有可能的路径，然后将这些路径数目加起来即为答案。

但是这样会存在许多重复计算。我们可以定义节点的前缀和来减少重复计算。

• 节点的前缀和：从根节点到当前节点路径上所有节点的和。

有了节点的前缀和，我们就可以通过前缀和来计算两节点之间的路劲和。即：则两节点之间的路径和 = 两节点之间的前缀和之差。

为了计算符合要求的路径数量，我们用哈希表存储「前缀和的节点数量」。哈希表以「当前节点的前缀和」为键，以「该前缀和的节点数量」为值。这样就能通过哈希表直接计算出符合要求的路径数量，从而累加到答案上。

整个算法的具体步骤如下：

• 通过先序遍历方式递归遍历二叉树，计算每一个节点的前缀和 cur_sum。
• 从哈希表中取出 cur_sum - target_sum 的路径数量（也就是表示存在从前缀和为 cur_sum - target_sum 所对应的节点到前缀和为 cur_sum 所对应的节点的路径个数）累加到答案 res 中。
• 然后以「当前节点的前缀和」为键，以「该前缀和的节点数量」为值，存入哈希表中。
• 递归遍历二叉树，并累加答案值。
• 恢复哈希表「当前前缀和的节点数量」，返回答案。

代码