给你二叉树的根节点 root 和一个整数目标和 targetSum ，找出所有 从根节点到叶子节点 路径总和等于给定目标和的路径。
叶子节点 是指没有子节点的节点。
示例 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：
输入：root = [1,2,3], targetSum = 5
输出：[]
示例 3：
输入：root = [1,2], targetSum = 0
输出：[]
提示：
- 树中节点总数在范围 [0, 5000] 内
- -1000 <= Node.val <= 1000
- -1000 <= targetSum <= 1000
分析：
方法：DFS+回溯?
不难看出，这是一道深度遍历（DFS）题，我们可以定义 List 集合来存储每个路径的节点，在定义结果集合 来存储 List 集合，当前节点遍历前，添加该节点的值到 List 集合中，当前节点遍历完后，删除该节点，回溯，当遍历到叶子结点时，判断此时的路径和是否和 targetSum 相同，相同将?List 集合添加到结果集合中。注意：直接添加 List 集合的地址是一样，因此要复制之后再添加 List 集合。
时间复杂度：O(n)?
空间复杂度：O(n)
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
//创建List集合存储路径
List<Integer> list = new LinkedList<>();
//创建List集合存储存储路径的List集合
List<List<Integer>> res = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int target) {
//空树直接返回
if(root == null){
return res;
}
//遍历
dfs(root, target);
return res;
}
public void dfs(TreeNode root, int target){
//遍历到叶子结点，判断是否走完
if(root.left == null && root.right == null){
//走完，添加路径
if(root.val == target){
//添加该节点
list.add(target);
//返回新的List集合
res.add(new LinkedList<>(list));
//删除该节点
list.remove(list.size()-1);
}
//没走完，回溯
return;
}
//遍历左节点
if(root.left != null){
//添加该节点到List集合
list.add(root.val);
//遍历左节点
dfs(root.left, target - root.val);
//删除该节点
list.remove(list.size()-1);
}
//遍历右节点
if(root.right != null){
//添加该节点到List集合
list.add(root.val);
//遍历右节点
dfs(root.right, target - root.val);
//删除该节点
list.remove(list.size()-1);
}
}
}题目来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof