Problem
Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values along the path equals targetSum. The paths can be returned in any order.A leaf node is a node with no left or right child.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
root = [5,4,8,11,null,13,4,7,2,null,null,5,1]
targetSum = 22
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1Output
[[5,4,11,2],[5,8,4,5]]Solution
This solution uses Depth-First Search (DFS) with recursion. As we traverse from the root toward a leaf, we add each node's value to the current path and subtract it from targetSum.When a leaf node is reached, we check whether its value makes the remaining sum zero. If it does, the current path represents a valid root-to-leaf path and is added to the result.
After exploring a subtree, the current node is removed from the path using backtracking. This allows the same path list to be reused while exploring other branches.
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
List<List<Integer>> result = new ArrayList<>();
List<Integer>> path = new ArrayList<>();
dfs(root, targetSum, path, result);
return result;
}
private void dfs(
TreeNode root,
int targetSum,
List<Integer> path,
List<List<Integer>> result) {
// Base case: no path exists.
if (root == null) {
return;
}
// Add the current node to the path.
path.add(root.val);
// Check whether the current leaf completes the target sum.
if (root.left == null && root.right == null
&& targetSum == root.val) {
result.add(new ArrayList<>(path));
}
// Explore both subtrees with the remaining sum.
int remainingSum = targetSum - root.val;
dfs(root.left, remainingSum, path, result);
dfs(root.right, remainingSum, path, result);
// Backtrack before returning to the parent.
path.remove(path.size() - 1);
}
}Complexity
In the worst case, every node in the binary tree may be visited, resulting in a time complexity ofO(n) for traversal. However, copying valid paths into the result can add additional cost proportional to the total size of the returned paths.
The recursive call stack can grow up to the height of the tree, while the current path also contains at most h nodes. Therefore, the auxiliary space complexity is
O(h), excluding the space required for the output.