AlgoPressAppearance
34-二叉树中和为某一值的路径
题目描述
https://leetcode.cn/problems/er-cha-shu-zhong-he-wei-mou-yi-zhi-de-lu-jing-lcof
给你二叉树的根节点 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
注意：本题与主站 113 题相同：https://leetcode.cn/problems/path-sum-ii/
思路分析
题目注意：需要遍历到叶子节点结束的才算，中间不算， 注意负数值
基本思路：中序深度遍历，创建临时数组 list ,当和为 sum 的时候，复制添加到总数组
每一步遍历完成时，移除最后一个元素，继续下次递归
测试用例
注意：1. 负数测试不通过: [-2,null,-3]
-5
判断 curSum == target 的时候，else 条件不能判断 curSum < target 继续，因为 可能和为负数，必然小于 target
2. 因为到判断到 叶子，所以，必须每次都判断下一级不能停止
[1,-2,-3,1,3,-2,null,-1]
-1
实现代码
csharp
/**
* Definition for a binary tree node.
* public class TreeNode {
* public int val;
* public TreeNode left;
* public TreeNode right;
* public TreeNode(int val=0, TreeNode left=null, TreeNode right=null) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
public class Solution {
private int CalcSum(List<int> list){
int sum = 0;
for(int i = 0; i < list.Count; i++){
sum += list[i];
}
return sum;
}
private List<int> CopyList(List<int> list){
List<int> newList = new List<int>();
for(int i = 0; i < list.Count; i++){
newList.Add(list[i]);
}
return newList;
}
//先序深度搜索 : 根左右
private void dfs(TreeNode node, int target, List<IList<int>> result, List<int> curList){
if(node != null){
curList.Add(node.val);
if(CalcSum(curList) == target && node.left == null && node.right == null){
result.Add(CopyList(curList));
}
dfs(node.left,target,result,curList);
dfs(node.right,target,result,curList);
curList.RemoveAt(curList.Count - 1);
}
}
public IList<IList<int>> PathSum(TreeNode root, int target) {
List<IList<int>> result = new List<IList<int>>();
List<int> curList = new List<int>();
dfs(root, target, result, curList );
return result;
}
}
实现代码：优化计算Sum的部分
csharp
public class Solution {
//思路 dfs 深度遍历，将元素加入 array 中，如果发现和为 target 且当前节点没有子节点
//则拷贝加入改结果到总的结果中
private IList<IList<int>> result = new List<IList<int>>();
private int curSum = 0;
private List<int> CopyList(List<int> arr){
List<int> newArr = new List<int>();
for(int i=0;i<arr.Count; i++){
newArr.Add(arr[i]);
}
return newArr;
}
private void dfs(TreeNode root, int target, List<int> arr){
if(root != null){
curSum += root.val;
arr.Add(root.val);
if(curSum == target && root.left == null && root.right == null){
result.Add(CopyList(arr));
}
dfs(root.left,target,arr);
dfs(root.right,target,arr);
curSum -= root.val;
arr.RemoveAt(arr.Count-1);
}
}
public IList<IList<int>> PathSum(TreeNode root, int target) {
List<int> arr = new List<int>();
dfs(root,target,arr);
return result;
}
}