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
15
â€‹
16
if (node.left == null && node.right == null && node.val == sum) {
17
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!

Backtracking: