Path Sum III
Medium · Graphs · Explanation and code example
Try Every Downward Path Start
How it works
A valid downward path may begin at any node. For each possible start, a DFS counts paths whose running sum reaches the target. Recursively repeat this count with starts in the left and right subtrees, covering all choices without requiring a path to end at a leaf.
Steps
- Count matching downward paths starting at the current root.
- Repeat the start search for both child subtrees.
- Add all three counts.
Complexity
- Time: O(nh), worst-case O(n²) for a chain.
- Space: O(h) recursion stack.
Things to watch for
- A matching path can stop at an internal node.
- Negative values mean searching must continue after a match.
- This is the simpler repeated-DFS approach; it is not the linear prefix-sum variant.
Python code example
class Solution:
def pathSum(self, root: TreeNode | None, summ: int) -> int:
if not root:
return 0
def dfs(root: TreeNode, summ: int) -> int:
if not root:
return 0
return (int(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))
C++ code example
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);
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.