【LeetCode】437. 路径总和 III

437. 路径总和 III（中等）

方法：前缀和

思路

1. 前缀和定义

   一个节点的前缀和就是该节点到根之间的路径和。

   如下图，节点 4 的前缀和为 7 （7 = 4 + 2 + 1）

   	  1
        /  \
       2    3
      / \    \
     4   5    6
    / \   \
   7   8   9
   1
   2
   3
   4
   5
   6
   7

2. 题目要求的是找出路径和等于给定数值的路径总数, 而： 两节点间的路径和 = 两节点的前缀和之差

   如下图，假如题目给定数值为5，节点1的前缀和为: 1，节点3的前缀和为: 1 + 2 + 3 = 6，则prefix(3) - prefix(1) == 5，所以 节点1 到 节点3 之间有一条符合要求的路径( 2 --> 3 )

                        1
                       / 
                      2    
                     / 
                    3   
                   / 
                  4  
   1
   2
   3
   4
   5
   6
   7

3. 因此，我们只用遍历整颗树一次，使用哈希表记录每个节点的「前缀和」和「该前缀和的节点数量」，记录数量是因为有出现复数路径的可能。

4. 将该节点的前缀和和 targetSum 相减，查询哈希表中该值的个数，将这个数量加到最终结果上。然后递归进入左右子树。

5. 状态恢复

   左右子树遍历完成之后，回到当前层，需要把当前节点添加的前缀和去除。避免回溯之后影响上一层。

   举个例子，下图中有两个值为2的节点（A, B)。

   当我们遍历到最右方的节点6时，对于它来说，此时的前缀和为2的节点只该有B, 因为从A向下到不了节点6(A并不是节点6的祖先节点)。

   如果我们不做状态恢复，当遍历右子树时，左子树中A的信息仍会保留在map中，那此时节点6就会认为A, B都是可追溯到的节点，从而产生错误。

         0
        /  \
       A:2  B:2
      / \    \
     4   5    6
    / \   \
   7   8   9
   1
   2
   3
   4
   5
   6
   7

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     long val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(long x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(long x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map<long, long> mp; // mp[前缀和] = 出现次数
    int pathSum(TreeNode* root, int targetSum) {
        // 根节点的“父节点”前缀和为0
        mp[0] = 1;
        return dfs(root, targetSum, 0);
    }
    int dfs(TreeNode* root, int targetSum, long pre) {
        if(root == nullptr) return 0;
        pre += root->val;   
        int res = mp[pre - targetSum];
        mp[pre] ++;
        res += dfs(root->left, targetSum, pre);
        res += dfs(root->right, targetSum, pre);
        // 当前节点的左右子树都遍历后删除
        mp[pre] --;
        return res;
    }
};
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
29
30
31

参考资料

1. 主要思路

2. 辅助理解