Dare2Solve
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.
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.
Base Case:
root
is null
), return an empty list.Depth-First Search (DFS):
currentSum
) and a list of nodes (path
) representing the current path from the root.currentSum
and include it in path
.currentSum
equals targetSum
and if the current node is a leaf (i.e., it has no children). If both conditions are met, add the current path
to the result list.path
(backtracking) to allow other paths to be explored.Return Result:
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.
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.
class Solution {
public:
vector<vector<int>> pathSum(TreeNode* root, int targetSum) {
vector<vector<int>> result;
vector<int> path;
function<void(TreeNode*, int)> 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;
}
};
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
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> result = new ArrayList<>();
List<Integer> path = new ArrayList<>();
helper(root, targetSum, 0, path, result);
return result;
}
private void helper(TreeNode node, int targetSum, int sum, List<Integer> path, List<List<Integer>> 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);
}
}
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;
};