力扣链接:路径总和
力扣链接:路径总和II
路径总和
package com.harrison.class08;
public class Code11_PathSum {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
public static boolean isSum=false;
public static void process(TreeNode x,int preSum,int sum){
if(x.left==null && x.right==null){
if(x.val+preSum==sum){
isSum=true;
}
return ;
}
preSum+=x.val;
if(x.left!=null){
process(x.left,preSum,sum);
}
if(x.right!=null){
process(x.right,preSum,sum);
}
}
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root==null){
return false;
}
isSum=false;
process(root,0,targetSum);
return isSum;
}
}
路径总和II
package com.harrison.class08;
import java.util.ArrayList;
import java.util.List;
public class Code12_PathSumII {
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode() {
}
TreeNode(int val) {
this.val = val;
}
TreeNode(int val, TreeNode left, TreeNode right) {
this.val = val;
this.left = left;
this.right = right;
}
}
public static List> pathSum(TreeNode root, int targetSum) {
List> ans=new ArrayList<>();
if(root==null){
return ans;
}
List path=new ArrayList<>();
process(root,path,0,targetSum,ans);
return ans;
}
// path:之前已经形成的路径和的路径
// preSum:之前已经形成的路径和
// sum:要求凑够的目标
// ans:已经找到的答案
public static void process(TreeNode x,List path,int preSum,int sum,List> ans){
if(x.left==null && x.right==null){
if(x.val+preSum==sum){
path.add(x.val);
ans.add(copy(path));
path.remove(path.size()-1);// 经典的恢复现场
}
return ;
}
path.add(x.val);
preSum+=x.val;
if(x.left!=null){
process(x.left,path,preSum,sum,ans);
}
if(x.right!=null){
process(x.right,path,preSum,sum,ans);
}
path.remove(path.size()-1);
}
public static List copy(List list){
List ans=new ArrayList<>();
for(Integer i:list){
ans.add(i);
}
return ans;
}
}



