LeetCode Solutions
437. Path Sum III
Time: $O(n\log n) \to O(n^2)$ Space: $O(\log n) \to O(n)$
class Solution {
public:
int pathSum(TreeNode* root, int sum) {
if (root == nullptr)
return 0;
return dfs(root, sum) +
pathSum(root->left, sum) +
pathSum(root->right, sum);
}
private:
int dfs(TreeNode* root, int sum) {
if (root == nullptr)
return 0;
return (sum == root->val) +
dfs(root->left, sum - root->val) +
dfs(root->right, sum - root->val);
}
};
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);
}
}
class Solution:
def pathSum(self, root: TreeNode, summ: int) -> int:
if not root:
return 0
def dfs(root: TreeNode, summ: int) -> int:
if not root:
return 0
return (summ == root.val) + \
dfs(root.left, summ - root.val) + \
dfs(root.right, summ - root.val)
return dfs(root, summ) + \
self.pathSum(root.left, summ) + \
self.pathSum(root.right, summ)