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);
}
}
二元樹題目 = 溫柔善良