437. 路径总和 III

要求:路径方向向下,总和为target
思路:
法一:暴力遍历,对每个节点,往下查其和是否为target,注意查到还不能返回,因为后面可能有负数。击败50,83

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void dfs(TreeNode* root,int &targetSum,int &ans){
        if(root==nullptr)return;
        cal(root,targetSum,ans);
        dfs(root->left,targetSum,ans);
        dfs(root->right,targetSum,ans);
    }
    void cal(TreeNode* root,int targetSum,int &ans){
        if(root==nullptr)return;
        if(targetSum==root->val)++ans;
        cal(root->left,targetSum-root->val,ans);
        cal(root->right,targetSum-root->val,ans);
    }
    int pathSum(TreeNode* root, int targetSum) {
        if(root==nullptr)return 0;
        int ans=0;
        dfs(root,targetSum,ans);
        return ans;
    }
};

法二:上面是以某节点为起点的路径,且会出现重复遍历。可以考虑以某节点为结尾的路径,遍历到某节点时,找前面有几个点到该点为target,即sum[b]-sum[a]=target,前缀和,明显得先统计完当前的再往下遍历(左右),统计就是看哈希表sum[b]-target出现次数,哈希表存的是元素出现的次数,要注意的是,本解法好处在于一次遍历即可。注意sum[0]有一条即都不选

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map<int,int> sum;
    int ans;
    void dfs(TreeNode* root,int &targetSum,int cursum){
        if(root==nullptr)return;
        cursum+=root->val;
        ans+=sum[cursum-targetSum];
        sum[cursum]++;
        dfs(root->left,targetSum,cursum);
        dfs(root->right,targetSum,cursum);
        sum[cursum]--;
    }
    int pathSum(TreeNode* root, int targetSum) {
        if(root==nullptr)return 0;
        ans=0;
        sum[0]=1;
        dfs(root,targetSum,0);
        return ans;
    }
};
上一篇:2021-年终总结


下一篇:C# COM组件 踩坑总结