1，题目：
2，思路：
回溯法（先序遍历+路径记录）：
思路： 1.先序遍历： 按照 “根、左、右” 的顺序，遍历树的所有节点。 2.路径记录： 在先序遍历中，记录从根节点到当前节点的路径。当路径为 ① 根节点到叶节点形成的路径 且 ② 各节点值的和等于目标值 sum 时，将此路径加入结果列表。
算法流程：
pathSum(root, sum) 函数：
1.初始化： 结果列表 res ，路径列表 path 。2.返回值： 返回 res 即可。recur(root, tar) 函数：
1.递推参数： 当前节点 root ，当前目标值 tar 。2.终止条件： 若节点 root 为空，则直接返回。3.递推工作：4.路径更新： 将当前节点值 root.val 加入路径 path ；5.目标值更新： tar = tar - root.val（即目标值 tar 从 sum 减至 0 ）；6.路径记录： 当 ① root 为叶节点 且 ② 路径和等于目标值 ，则将此路径 path 加入 res 。7.先序遍历： 递归左 / 右子节点。8.路径恢复： 向上回溯前，需要将当前节点从路径 path 中删除，即执行 path.pop() 。下面是对应的图解：
3，代码：
回溯法（先序遍历+路径记录）：
class Solution { /* 1.先序遍历： 按照 “根、左、右” 的顺序，遍历树的所有节点。 2.路径记录： 在先序遍历中，记录从根节点到当前节点的路径。当路径为 ① 根节点到叶节点形成的路径 且 ② 各节点值的和等于目标值 sum 时，将此路径加入结果列表。 算法流程： pathSum(root, sum) 函数： 1.初始化： 结果列表 res ，路径列表 path 。 2.返回值： 返回 res 即可。 recur(root, tar) 函数： 1.递推参数： 当前节点 root ，当前目标值 tar 。 2.终止条件： 若节点 root 为空，则直接返回。 3.递推工作： 4.路径更新： 将当前节点值 root.val 加入路径 path ； 5.目标值更新： tar = tar - root.val（即目标值 tar 从 sum 减至 0 ）； 6.路径记录： 当 ① root 为叶节点 且 ② 路径和等于目标值 ，则将此路径 path 加入 res 。 7.先序遍历： 递归左 / 右子节点。 8.路径恢复： 向上回溯前，需要将当前节点从路径 path 中删除，即执行 path.pop() 。 */ LinkedList<List<Integer>> res = new LinkedList<>(); LinkedList<Integer> path = new LinkedList<>(); public List<List<Integer>> pathSum(TreeNode root, int sum) { recur(root, sum); return res; } void recur(TreeNode root, int tar) { if(root == null) return; path.add(root.val); tar -= root.val; if(tar == 0 && root.left == null && root.right == null) res.add(new LinkedList(path)); recur(root.left, tar); recur(root.right, tar); path.removeLast(); } }写法二：思路和上面的是一样的，只不过是写法不一样：
class Solution { public List<List<Integer>> pathSum(TreeNode root, int sum) { List<List<Integer>> lists = new ArrayList<>(); if(root == null) return lists; findPath(new ArrayList<Integer>(),root,sum,0,lists); return lists; } /* * path:用于存放当前节点所在的路径（随着遍历一直在变动） */ private static void findPath(List<Integer> path, TreeNode node, int sum, int tempSum,List<List<Integer>> lists) { //到当前节点位置的路径的节点值的和 tempSum += node.val; // path.add(node.val); if(tempSum == sum && node.left == null &&node.right == null) { //得到一个符合要求的路径时，创建一个新的ArrayList，拷贝当前路径到其中，并添加到lists中 lists.add(new ArrayList(path)); } if(node.left != null) { findPath(path,node.left,sum,tempSum,lists); //递归结束时，该留的路径已经记录了，不符合的路径也都不用理，删掉当前路径节点的值 path.remove(path.size()-1); } if(node.right != null) { findPath(path,node.right,sum,tempSum,lists); //递归结束时，该留的路径已经记录了，不符合的路径也都不用理，删掉当前路径节点的值 path.remove(path.size()-1); } } }