面试题 04.12. 求和路径

面试题 04.12. 求和路径 #

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

题目大意 #

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

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

  • 路径:不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的(只能从父节点到子节点)。

解题思路 #

直观想法是:

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

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

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

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

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

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

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

代码 #

1

本站总访问量  次  |  您是本站第  位访问者