Problem
Given a binary tree and a sum, find all root-to-leaf paths where each path’s sum equals the given sum.
Examples
Example 1:
graph TD; A[5] --> B[4] & C[8] B --> D[11] & E[null] C --> F[13] & G[4] D --> H[7] & I[2] G --> L[5] & M[1] style A fill:#f9f style B fill:#f9f style C fill:#f9f style D fill:#f9f style I fill:#f9f style G fill:#f9f style L fill:#f9f
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output:[[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
Solution
Method 1 - Recursive DFS
This problem can be converted to be a typical depth-first search problem. A recursive depth-first search algorithm usually requires a recursive method call, a reference to the final result, a temporary result, etc.
Code
Java
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
helper(root, sum, new ArrayList<Integer>(), ans);
return ans;
}
private void helper(TreeNode root, int sum, List<Integer> subAns, List<List<Integer>> ans) {
if (root == null) {
return;
}
subAns.add(new Integer(root.val));
if (root.left == null && root.right == null && sum == root.val) {
ans.add(new ArrayList(subAns));
} else {
helper(root.left, sum - root.val, subAns, ans);
helper(root.right, sum - root.val, subAns, ans);
}
subAns.remove(subAns.size() - 1); // backtrack
}
Complexity
- ⏰ Time complexity:
O(n^2)
. - First, we think the time complexity isO(n)
because we only visit each node once. - But we forgot to calculate the cost to copy the current
path
when we found a valid path, which in the worst case can costO(n^2)
- 🧺 Space complexity:
O(h)
assuming recursive stack…in worst caseh = n
.