【leetcode】【剑指offer Ⅱ】050. 向下的路径节点之和

问题描述：

• 给定一个二叉树的根节点 root，和一个整数 targetSum，求该二叉树里节点值之和等于 targetSum 的路径的数目。
  • 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

核心思路：

• 该题同样可用 dfs 解法来解决，但与普通的二叉树基础应用题不同，该题需要双重递归遍历才可以解决。
  • 内部递归以当前根节点 root 与目标值 target 作为参数，不断在递归过程中向下更新 target（也就是 target -= root->val），当在某个节点处 target 更新为 0，则结果计数器加一。
  • 而外部递归在开始时都将计数器清零，将 target 传递给下一层外部递归（也就是说，外部递归就是遍历每一个节点，将 target 传给每一个节点），同时对当前节点进行内部递归，内部递归得出的计数器结果与左右子返回的结果相加即可。
  • 简单来说，我们访问每一个节点（外部递归），检测以为起始节点且向下延深的路径有多少种（内部递归）。
• 该题还有一种前缀和优化的解法。【该解法是单重递归遍历】
  • 要理解起来也很容易，二叉树的单条向下路径其实可以看作是单向链表，因而可以在递归访问单链的过程中维护之前的前缀和，而通过前缀和的差值就可以判断相应区间的和是否等于 target。
  • 由于单条向下路径可以看作是单链，而二叉树中又存在很多条向下路径，所以在当前节点递归访问完子节点，当前函数准备返回之时，需要将维护前缀和的数据结构恢复如初。【也就是回溯的思想】
    • 简单来说，用哈希表 prefix 保存前缀和出现的次数，在当前节点，前缀为 cur，则进入子节点递归前 ++prefix[cur]（更新哈希表后进入递归），递归结束后当前函数返回前 --prefix[cur]（回溯到原来状态）。

代码实现：

• dfs 解法代码实现如下：

  class Solution
  {
  private:
      int ans = 0;
      void dfs(TreeNode* root, int target)
      {
          if(!root) return;
          target -= root->val;
          if(target == 0) ++ans;
          dfs(root->left, target);
          dfs(root->right, target);
      }
  public:
      int pathSum(TreeNode* root, int targetSum)
      {
          ans = 0;
          if(!root) return ans;
          dfs(root, targetSum);
          return ans + pathSum(root->left, targetSum) + pathSum(root->right, targetSum);
      }
  };
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21

• 前缀和优化解法代码实现如下：【贴自官方题解】

  class Solution {
  public:
      unordered_map<long long, int> prefix;
  
      int dfs(TreeNode *root, long long curr, int targetSum) {
          if (!root) {
              return 0;
          }
  
          int ret = 0;
          curr += root->val;
          if (prefix.count(curr - targetSum)) {
              ret = prefix[curr - targetSum];
          }
  
          prefix[curr]++;
          ret += dfs(root->left, curr, targetSum);
          ret += dfs(root->right, curr, targetSum);
          prefix[curr]--; // 回溯
  
          return ret;
      }
  
      int pathSum(TreeNode* root, int targetSum) {
          prefix[0] = 1; // 注意要把空集的次数放入
          return dfs(root, 0, targetSum);
      }
  };
  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