给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
示例:
给定如下二叉树，以及目标和 sum = 22，
5
/ \
4 8
/ / \
11 13 4
/ \ / \
7 2 5 1
返回:
[
[5,4,11,2],
[5,8,4,5]
]
答案：
1public List<List<Integer>> pathSum1(TreeNode root, int sum) {
2 List<List<Integer>> result = new LinkedList<List<Integer>>();
3 List<Integer> currentResult = new LinkedList<Integer>();
4 pathSum(root, sum, currentResult, result);
5 return result;
6}
7
8public void pathSum(TreeNode root, int sum, List<Integer> currentResult,
9 List<List<Integer>> result) {
10 if (root == null)
11 return;
12 currentResult.add(new Integer(root.val));
13 if (root.left == null && root.right == null && sum == root.val) {
14 result.add(new LinkedList(currentResult));
15 } else {
16 pathSum(root.left, sum - root.val, currentResult, result);
17 pathSum(root.right, sum - root.val, currentResult, result);
18 }
19 currentResult.remove(currentResult.size() - 1);
20}
解析：
这里主要使用的递归加回溯的思想，在第12行把当前节点的值添加到集合中，在第19行回溯。如果对DFS（深度优先搜索）比较熟悉的话，上面代码就非常容易理解了。下面再来换种写法
1public List<List<Integer>> pathSum(TreeNode root, int sum) {
2 List<List<Integer>> res = new ArrayList<>();
3 List<Integer> path = new ArrayList<>();
4 dfs(root, sum, res, path);
5 return res;
6}
7
8public void dfs(TreeNode root, int sum, List<List<Integer>> res, List<Integer> path) {
9 if (root == null) return;
10 path.add(root.val);
11 if (root.left == null && root.right == null && root.val == sum) {
12 res.add(new ArrayList<Integer>(path));
13 return;
14 }
15 if (root.left != null) {
16 dfs(root.left, sum - root.val, res, path);
17 path.remove(path.size() - 1);
18 }
19 if (root.right != null) {
20 dfs(root.right, sum - root.val, res, path);
21 path.remove(path.size() - 1);
22 }
23}
原理都是一样的。