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
  
1
2
3
4
5

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

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 is O(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 cost O(n^2)
  • 🧺 Space complexity: O(h) assuming recursive stack…in worst case h = n.