## Path Sum III

• Time:O(n\log n) \to O(n^2)
• Space:O(\log n) \to O(n)

## C++

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

private:
int dfs(TreeNode* root, int sum) {
if (!root)
return 0;
return (sum == root->val) +
dfs(root->left, sum - root->val) +
dfs(root->right, sum - root->val);
}
};


## JAVA

class Solution {
public int pathSum(TreeNode root, int sum) {
if (root == null)
return 0;
return dfs(root, sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
}

private int dfs(TreeNode root, int sum) {
if (root == null)
return 0;
return (sum == root.val ? 1 : 0) +
dfs(root.left, sum - root.val) +
dfs(root.right, sum - root.val);
}
}


## Python

class Solution:
def pathSum(self, root: TreeNode, sum: int) -> int:
if not root:
return 0

def dfs(root: TreeNode, sum: int) -> int:
if not root:
return 0
return (sum == root.val) + \
dfs(root.left, sum - root.val) + \
dfs(root.right, sum - root.val)

return dfs(root, sum) + \
self.pathSum(root.left, sum) + \
self.pathSum(root.right, sum)