双递归,时间复杂度$O(nlogn)$
/**
* 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:
int count = 0;
int pathSum(TreeNode* root, int sum) {
if(root == nullptr) return 0;
dfs(root,sum);
pathSum(root->left,sum); //对原树的每一个节点都调用一次
pathSum(root->right,sum);
return count;
}
void dfs(TreeNode* root,int sum){
if(root == nullptr) return ;
if(sum-root->val == 0) count++;
dfs(root->left,sum-root->val);
dfs(root->right,sum-root->val);
}
};
前缀和
/**
* 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> count;
int pathSum(TreeNode* root, int sum) {
count[0] = 1;
return helper(root,sum,0);
}
int helper(TreeNode* root,int sum,int prefix_sum){
if(root == nullptr) return 0;
int res= 0;
prefix_sum += root->val;
res += count[prefix_sum-sum];
count[prefix_sum]++;
res += helper(root->left,sum,prefix_sum) + helper(root->right,sum,prefix_sum);
count[prefix_sum] -- ;
return res;
}
};