``````/**
* 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 pathSum(TreeNode* root, int sum) {
if(root)
{
dfs(root,sum);
pathSum(root->left,sum);
pathSum(root->right,sum);
}
return ans;
}
private:
int ans = 0;
void dfs(TreeNode* root,int sum) {
if(!root) return;
if(root->val == sum)
ans += 1;
dfs(root->left,sum - root->val);
dfs(root->right,sum - root->val);
}
};``````

``````Runtime: 32 ms, faster than 28.32% of C++ online submissions for Path Sum III.
Memory Usage: 15.7 MB, less than 83.58% of C++ online submissions for Path Sum III.``````

``````/**
* 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 pathSum(TreeNode* root, int sum) {
if(!root) return 0;
return pathSum(root,0,sum) + pathSum(root->left,sum) + pathSum(root->right,sum);
}
private:
int pathSum(TreeNode* root,int pre,int sum) {
if(!root) return 0;
int current = pre + root->val;
return (sum == current) + pathSum(root->left,current,sum) + pathSum(root->right,current,sum);
}
};``````

``````Runtime: 32 ms, faster than 28.32% of C++ online submissions for Path Sum III.
Memory Usage: 15.5 MB, less than 92.29% of C++ online submissions for Path Sum III.``````