Path Sum II
Medium · Graphs · Explanation and code example
Depth-First Search with Backtracking
How it works
Track the values on the current root-to-node path and the target still needed. Only a leaf can complete a root-to-leaf path. Copy a successful path into the output, then remove the current node when returning so sibling searches start with the correct prefix.
Steps
- Append the node and reduce the remaining target.
- At a leaf, save the path if the remaining sum matches.
- Visit children, then pop the node from the path.
Complexity
- Time: O(n + K), where K is the total number of values in returned paths.
- Space: O(h) working space plus O(K) output, for tree height h.
Things to watch for
- A matching internal-node sum is not a completed path.
- Negative values prevent pruning simply because the remaining target is negative.
- Copy saved paths before backtracking.
Python code example
class Solution:
def pathSum(self, root: TreeNode | None, targetSum: int) -> list[list[int]]:
result, path = [], []
def dfs(node, remaining):
if node is None:
return
path.append(node.val)
remaining -= node.val
if node.left is None and node.right is None and remaining == 0:
result.append(path.copy())
dfs(node.left, remaining)
dfs(node.right, remaining)
path.pop()
dfs(root, targetSum)
return result
C++ code example
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int sum) {
vector<vector<int>> ans;
dfs(root, sum, {}, ans);
return ans;
}
private:
void dfs(TreeNode* root, int sum, vector<int>&& path,
vector<vector<int>>& ans) {
if (root == nullptr)
return;
if (root->val == sum && root->left == nullptr && root->right == nullptr) {
path.push_back(root->val);
ans.push_back(path);
path.pop_back();
return;
}
path.push_back(root->val);
dfs(root->left, sum - root->val, std::move(path), ans);
dfs(root->right, sum - root->val, std::move(path), ans);
path.pop_back();
}
};
Source and license
Explanation by LC Tracker. Code adapted from walkccc / Peng-Yu Chen · MIT license. Node types are supplied by LeetCode where needed.