给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。
说明: 叶子节点是指没有子节点的节点。
解题思路
与上一题思路基本一致，只需要将过程中的路径保存起来
注意将结果添加至结果集时要new一个链表result.add(new ArrayList<>(path))
如果直接添加，只是添加了当前链表的引用，随后链表发生变化会改变结果集中的元素
代码
class Solution {
public List<List<Integer>> pathSum(TreeNode root, int sum) {
List<List<Integer>> result = new LinkedList<>();
if (root == null) {
return result;
}
LinkedList<Integer> path = new LinkedList<>();
dfs(root, sum, path, result);
return result;
}
private void dfs(TreeNode root, int sum, LinkedList<Integer> path, List<List<Integer>> result) {
if (root == null) {
return;
}
path.addLast(root.val);
if (root.left == null && root.right == null) {
if (sum - root.val == 0) {
result.add(new ArrayList<>(path));
}
} else { // 如果不是叶节点
dfs(root.left, sum - root.val, path, result);
dfs(root.right, sum - root.val, path, result);
}
path.removeLast();
}
}
