113 Path Sum II

113. Path Sum II

1. Question

Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and
sum = 22,
1
5
2
/ \
3
4 8
4
/ / \
5
11 13 4
6
/ \ / \
7
7 2 5 1
Copied!
return
1
[
2
[5,4,11,2],
3
[5,8,4,5]
4
]
Copied!

2. Implementation

(1) Backtracking
1
class Solution {
2
public List<List<Integer>> pathSum(TreeNode root, int sum) {
3
List<List<Integer>> res = new ArrayList<>();
4
List<Integer> path = new ArrayList<>();
5
getPathSum(root, 0, sum, path, res);
6
return res;
7
}
8
9
public void getPathSum(TreeNode node, int depth, int sum, List<Integer> path, List<List<Integer>> res) {
10
if (node == null) {
11
return;
12
}
13
14
path.add(node.val);
15
16
if (node.left == null && node.right == null && node.val == sum) {
17
res.add(new ArrayList(path));
18
}
19
20
getPathSum(node.left, depth + 1, sum - node.val, path, res);
21
getPathSum(node.right, depth + 1, sum - node.val, path, res);
22
23
path.remove(path.size() - 1);
24
}
25
}
Copied!

3. Time & Space Complexity

Backtracking: