AlgoPressAppearance
0113-路径总和II
https://leetcode.cn/problems/path-sum-ii
给你二叉树的根节点 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 先序遍历(根左右)，每次遍历，将数组压入list, targetSum 减去 节点值 如果 targetSum == 0 ， 则判断是否叶子节点，是的话，复制list到最终 list 中去，否则继续判断
参考代码
csharp
public class Solution {
private List<int> CopyList(List<int> input){
List<int> newList = new List<int>();
for(int i = 0; i < input.Count; i++){
newList.Add(input[i]);
}
return newList;
}
private void FindPathSum(List<IList<int>> result, List<int> curList, TreeNode node, int targetSum){
if(node == null){
return;
}
curList.Add(node.val);
targetSum -= node.val;
if(targetSum == 0){
if(node.left == null && node.right == null){
result.Add(CopyList(curList));
}
}
//此处不要用 else 判断，因为前面结果可能也为0了，但是不是叶子节点，后面还可以在计算总的和为0，可以输出
FindPathSum(result, curList, node.left, targetSum);
FindPathSum(result, curList, node.right, targetSum);
targetSum += node.val;
curList.RemoveAt(curList.Count -1);
}
public IList<IList<int>> PathSum(TreeNode root, int targetSum) {
List<IList<int>> result = new List<IList<int>>();
List<int> curList = new List<int>();
FindPathSum(result, curList, root, targetSum);
return result;
}
}
参考代码：复习20220508
csharp
public class Solution {
List<int> list;
List<IList<int>> result;
private void dfs(TreeNode node, int targetSum){
if(node == null){
return;
}
list.Add(node.val);
if(node.left == null && node.right == null){
//叶子节点计算 sum;
if(targetSum == node.val){
//复制节点
List<int> newList = new List<int>(list.ToArray());
result.Add(newList);
}
}
else{
dfs(node.left, targetSum - node.val);
dfs(node.right, targetSum - node.val);
}
list.RemoveAt(list.Count-1);
}
public IList<IList<int>> PathSum(TreeNode root, int targetSum) {
list = new List<int>();
result = new List<IList<int>>();
dfs(root,targetSum);
return result;
}
}