一、题目
给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。叶子节点 是指没有子节点的节点。
二、示例
2.1> 示例 1：
【输入】root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22 【输出】[[5,4,11,2],[5,8,4,5]]
2.2> 示例 2：
【输入】root = [1,2,3], targetSum = 5 【输出】[]
2.3> 示例 3：
【输入】root = [1,2], targetSum = 0 【输出】[]
提示：
- • 树中节点总数在范围
[0, 5000] - •
-1000<= Node.val <=1000 - •
-1000<= targetSum <=1000
三、解题思路
根据题目要求，我们需要寻找N条从根路径到叶子节点的路径，并要求满足该路径节点之和等于targetSum；既然涉及到二叉树节点遍历，常用的就是深度优先算法和广度优先算法，那么由于本题涉及从根路径到叶子节点的路径，那么我们可以采用深度优先算法 前序遍历对这道题进行解答。
其实本题的一个难点就是如何去拼装最终结果List<List<Integer>> result，那么既然是需要获得满足条件的路径节点值的集合，我们就可以创建一个变量LinkedList<Integer> path，用于记录当前所经过的节点值。那么当我们从根节点遍历到叶子节点之后，会有如下两种情况：
【情况1】所有节点总和正好等于
targetSum，那么我们通过复制path，然后保存到result中即可。如果还有其他树节点需要遍历，逐一回溯path末尾节点val值。 【情况2】所有节点总和不等于targetSum，如果还有其他树节点需要遍历，逐一回溯path末尾节点val值。
需要注意的是，当我们确认某一条路径等于targetSum之后，我们需要“复制”该路径（即：通过new LinkedList(path)）否则路径就会随着回溯操作而发生变化了。上面就是具体的解题思路，下面我们还是以输入：root = [5,4,8,11,null,13,4,7,2,null,null,5], targetSum = 22为例，看一下具体的操作过程是怎么样的。请见下图所示：
四、代码实现
代码语言：javascript复制class Solution {
List<List<Integer>> result;
LinkedList<Integer> path;
public List<List<Integer>> pathSum(TreeNode root, int target) {
result = new LinkedList();
path = new LinkedList();
dfs(root, target);
return result;
}
public void dfs(TreeNode node, int value) {
if (node == null) return;
path.addLast(node.val);
if (node.val == value && node.left == null && node.right == null)
result.add(new LinkedList(path));
dfs(node.left, value - node.val);
dfs(node.right, value - node.val);
path.removeLast(); // 回溯
}
}
