2021.9.28打卡

遍历每个节点，以该节点向下的路径有几种满足条件。递归遍历每个节点的所有可能路径，将这些路径数加起来返回结果。

pathSum：该节点为起始点(不一定从该点出发)的路径满足条件数目

getSum：该节点为根节点的路径满足条件数目

class Solution {
public:
    int pathSum(TreeNode* root, int targetSum) {
        if(!root)
            return 0;
        int ret=getSum(root,targetSum);
        ret+=pathSum(root->left,targetSum);
        ret+=pathSum(root->right,targetSum);
        return ret;
    }

    int getSum(TreeNode* root,int targetSum){
        if(!root)
            return 0;
        int ret=0;
        if(root->val==targetSum)
            ret++;
        ret+=getSum(root->left,targetSum-root->val);
        ret+=getSum(root->right,targetSum-root->val);
        return ret;
    }
};

时间复杂度：O(n^2) 遍历每个节点，对每个节点求该店为起点的路径数目。

空间复杂度：O(n)

前面的解法存在重复计算。定义前缀和为：根结点到当前结点的路径上所有结点之和。先序遍历二叉树，记录根节点到当前节点的前缀和，在已保存的前缀和中查找是否存在前缀和等于当前前缀和curr减去targetSum

• 对于空节点，前缀和为0
• 当前从根节点到node节点的前缀和为curr，此时查看我们保存的前缀和中是否有前缀和等于curr-targetSum
• 当退出当前节点，需要及时更新前缀和

class Solution {
public:

    unordered_map prefix;

    int pathSum(TreeNode* root, int targetSum) {
        if(!root)
            return 0;
        prefix[0]=1;
        return dfs(root,0,targetSum);
    }

    int dfs(TreeNode* root,long long curr,int targetSum){
        if(!root)
            return 0;
        curr+=root->val;
        int ret=0;
        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;
    }
};