题目描述
思路
代码
−109<=Node.val<=109
二叉树的节点个数的范围是 [0,1000]
而int的范围为2×10^9^ 或 2^31^-1
那么sum很有可能就爆了int,所以得开unordered_map<long long,int> mp;
/**
* 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 {
private:
unordered_map<long long,int> mp; //哈希表
int res=0;
public:
int pathSum(TreeNode* root, int targetSum) {
mp.insert({0,1}); //这里其实是算的从根结点到目的结点的路径,是有一条的
//因为sum-targetSum=0时,其实表示的就是从根节点到目的结点的路径
dfs(root,0,targetSum);
return res;
}
void dfs(TreeNode* root,long long sum,int targetSum)
{
if(!root) return; //如果该节点为空
sum += root->val; //先把前缀和加上
if(mp.count(sum-targetSum)) res+=mp[sum-targetSum];
if(mp.count(sum)) mp[sum]++;
else mp.insert({sum,1});
dfs(root->left,sum,targetSum);
dfs(root->right,sum,targetSum);
mp[sum]--;
}
};