题⽬描述

给定⼀个⼆叉树root和⼀个整数值 sum，求该树有多少路径的的节点值之和等于 sum 。

  1. 该题路径定义不需要从根节点开始，也不需要在叶⼦节点结束，但是⼀定是从⽗亲节点往下到孩⼦节点

  2. 总节点数⽬为 n

  3. 保证最后返回的路径个数在整形范围内

假如⼆叉树 root 为 {1,2,3,4,5,4,3,#,#,-1}， sum=6，那么总共如下所示，

思路及解答

双重递归法（暴力解法）

外层递归遍历所有节点作为起点，内层递归计算从该点向下的路径和

  • 时间复杂度：O(n²)，最坏情况下每个节点都要递归遍历其子树

  • 空间复杂度：O(n)，递归栈深度

记忆化递归法

使用记忆化技术缓存计算结果，为每个节点存储从该节点向下的路径和计数，优化递归效率。

  • 时间复杂度：O(n)，每个节点计算一次

  • 空间复杂度：O(n)，缓存所有节点结果

前缀和哈希表（最优解）

从根节点到当前节点的路径和curSum，查找curSum-targetSum是否存在

前缀和核心思想：

  • 路径和 = 当前前缀和 - 之前某个前缀和

  • curSum - targetSum是否存在于前缀和哈希表中

  • 如果存在，说明从那个节点到当前节点的路径和为targetSum

执行示例（树[10,5,-3,3,2,null,11,3,-2,null,1]，sum=8）：

  • 时间复杂度：O(n)，每个节点只访问一次

  • 空间复杂度：O(n)，哈希表存储n个前缀和