//路径累加和

//路径累加和

package PathSum;
 
/**
 * @author 真他喵的学不动咯
 * @create 2022-08-16--21:26
 */
public class Path {   //路径累加和
    //https://leetcode.com/problems/path-sum/
    //路径：必须头结点开始，叶节点结束
 
    public static class TreeNode{
        public int val;
        public TreeNode left;
        public TreeNode right;
        TreeNode(int val){
            this.val=val;
        }
    }
 
    public static boolean isSum=false;  //全局变量的方法
    public static boolean hasPathSum(TreeNode root,int sum){
        if (root==null){    //没到根节点就不是路径，那就不求和
            return false;
        }
        isSum=false;        //每次都把它变成了false，重新判断
        process(root,0,sum);  //找是否有路径能够达到要求的和
        return isSum;
    }
    public static void process(TreeNode x,int preSum,int sum){  //preSum是之前的累加和 ，sum是要求的累加和，x是树
        if (x.left==null&&x.right==null){  //如果x的左和右都是null，那就是叶节点；只有一面是null，就未必是叶节点
            //这条路径是不是能凑出要求的sum
            if (x.val+preSum==sum){        //x.val+preSum就是当前元素+之前的累加和
                isSum=true;  //isSum表示是不是能凑出这个和sum，isSum是true和false
            }
            return;
        }
        //x是非叶节点
        preSum=preSum+x.val;  //加入前缀和
        if (x.left!=null){   //左不空给左传，向有叶节点的方向传
            process(x.left,preSum,sum);
        }
        if (x.right!=null){   //右不空给右传，右边有叶节点
            process(x.right,preSum,sum);
        }
    }
    }