113. Path Sum II
给予一个二元树和一个target，求出根节点到叶子节点元素总和为target的所有Path。
Example：
https://assets.leetcode.com/uploads/2021/01/18/pathsumii1.jpg
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
思路：
1.用回溯法解。
2.利用一个List纪录当前走访过的元素，若路径和等于target且是叶子节点时将解加入
解集合。
JavaCode：
class Solution {
private List<List<Integer>> res;
public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
res = new ArrayList<>();
DFS(root, new ArrayList<>(), targetSum, 0);
return res;
}
private void DFS(TreeNode root, List<Integer> curr, int target, int sum) {
if(root == null)
return;
sum += root.val;
curr.add(root.val);
if(sum == target && root.left == null && root.right == null)
res.add(new ArrayList<>(curr));
DFS(root.left, curr, target, sum);
DFS(root.right, curr, target, sum);
curr.remove(curr.size() - 1);
}
}
二元树题目 = 温柔善良