50. 向下的路径节点之和.md

50. 向下的路径节点之和: DFS 前缀和

(1) DFS

DFS(root, target)用来遍历「严格以root为根节点的路径」, 对于满足target要求的计数

pathSum(root, target)遍历树中所有节点, 作为DFS(root, target)的根节点

满足条件的路径数量包括: DFS(root, targetsum), pathSum(root->left, targetSum)和pathSum(root->left, targetSum)

// 递归「严格以root为根」的路径, 对路径和为targetSum的计数
int DFS(TreeNode* root, long long targetSum){
    if(root == NULL)
        return 0;
    int cnt = 0;
    if(root->val == targetSum)
        cnt++;
    cnt += DFS(root->left, targetSum - root->val);
    cnt += DFS(root->right, targetSum - root->val);
    return cnt;
}
// 递归所有树的节点作为DFS的root
int pathSum(TreeNode* root, int targetSum) {
    if(root==NULL)
        return 0;
    // 这里DFS以当前节点为起点的树中的所有路径, 对和为targetSum的计数
    int ans = DFS(root, targetSum);
    // 这里DFS树中节点, 即枚举起点
    ans += pathSum(root->left, targetSum);
    ans += pathSum(root->right, targetSum);
    return ans;
}

(2) 前缀和解法

求一段路径的总和, 很像前缀和, 不过本题更在意当前路径上已经存在几个x-target, 而不注重在路径上的具体位置

于是就变成了「树状」的LC560. 和为K的子数组

初始化一个mp[0]=1, 表示空树

backtrack(root, sum, target):

• 将root->val加入sum
• 如果当前DFS路径上已经存在x-target, ans += mp[sum-target]
• 记录当前路径上的前缀和, mp[sum]++
• 递归左右子树
• 递归左右子树后要取消对sum的计数, mp[sum]--

unordered_map<long long, int> mp;   // 在当前路径上, 记录从root到cur上的pathSum出现的次数
int ans = 0;
void backtrack(TreeNode* root, long long pathSum, int targetSum){
    if(root==NULL)
        return ;
    pathSum += root->val;
    // 前缀和, 应该是pathSum - x = targetSum
    if(mp.find(pathSum-targetSum)!=mp.end())
        ans += mp[pathSum-targetSum];
    mp[pathSum]++;
    backtrack(root->left, pathSum, targetSum);
    backtrack(root->right, pathSum, targetSum);
    mp[pathSum]--;
}
int pathSum(TreeNode* root, int targetSum) {
    mp[0] = 1;
    backtrack(root, 0, targetSum);
    return ans;
}