
Description
The problem is to find all root-to-leaf paths in a binary tree where the sum of the node values equals a given targetSum
. Each path should be returned as a list of node values, and all such paths should be collected in a list of lists.
Intuition
To solve this problem, we can use a depth-first search (DFS) approach. The idea is to explore every possible path from the root to the leaf nodes, keeping track of the cumulative sum of node values along the way. If a path's sum equals the targetSum
and it ends at a leaf node, it is a valid path that should be included in the result.
Approach
- Base Case:
- If the tree is empty (i.e.,
root
isnull
), return an empty list. - Depth-First Search (DFS):
- Use a recursive function to traverse the tree. Start from the root node and explore each path by visiting left and right subtrees.
- Maintain a running sum of node values (
currentSum
) and a list of nodes (path
) representing the current path from the root. - At each node: - Add the node's value tocurrentSum
and include it inpath
. - Check ifcurrentSum
equalstargetSum
and if the current node is a leaf (i.e., it has no children). If both conditions are met, add the currentpath
to the result list. - Recursively explore the left and right subtrees. - After exploring a node's children, remove the node frompath
(backtracking) to allow other paths to be explored. - Return Result: - Once all paths have been explored, return the list of valid paths.
Complexity
Time Complexity:
The time complexity is (O(n)), where n
is the number of nodes in the tree. In the worst case, every node is visited once during the DFS.
Space Complexity:
The space complexity is (O(h)), where h
is the height of the tree. This is the space used by the recursion stack during DFS. In the worst case, the space complexity could be (O(n)) if the tree is skewed.
Code
C++
class Solution {
public:
vector> pathSum(TreeNode* root, int targetSum) {
vector> result;
vector path;
function rec = [&](TreeNode* node, int sum) {
if (!node) return;
sum += node->val;
path.push_back(node->val);
if (sum == targetSum && !node->left && !node->right) {
result.push_back(path);
} else {
rec(node->left, sum);
rec(node->right, sum);
}
path.pop_back();
};
rec(root, 0);
return result;
}
};
Python
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
if not root:
return []
result = []
def rec(node, currentSum, path):
if not node:
return
currentSum += node.val
path.append(node.val)
if currentSum == targetSum and not node.left and not node.right:
result.append(list(path))
else:
rec(node.left, currentSum, path)
rec(node.right, currentSum, path)
path.pop()
rec(root, 0, [])
return result
Java
class Solution {
public List> pathSum(TreeNode root, int targetSum) {
List> result = new ArrayList<>();
List path = new ArrayList<>();
helper(root, targetSum, 0, path, result);
return result;
}
private void helper(TreeNode node, int targetSum, int sum, List path, List> result) {
if (node == null) return;
sum += node.val;
path.add(node.val);
if (sum == targetSum && node.left == null && node.right == null) {
result.add(new ArrayList<>(path));
} else {
helper(node.left, targetSum, sum, path, result);
helper(node.right, targetSum, sum, path, result);
}
path.remove(path.size() - 1);
}
}
JavaScript
var pathSum = function (root, targetSum) {
if (!root) return [];
const r = [];
const rec = (node, sum, path) => {
if (!node) return;
const s = sum + node.val;
const p = [...path, node.val];
console.log(s)
if (s === targetSum && !node.left && !node.right) {
r.push(p);
return;
}
rec(node.left, s, p);
rec(node.right, s, p);
}
rec(root, 0, []);
return r;
};