路径总和

描述

给你二叉树的根节点?root 和一个表示目标和的整数?targetSum ，判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和?targetSum 。

叶子节点是指没有子节点的节点。

示例 1

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true

示例 2

输入：root = [1,2,3], targetSum = 5
输出：false

示例 3

输入：root = [1,2], targetSum = 0
输出：false

提示

树中节点的数目在范围 [0, 5000] 内
-1000 <= Node.val <= 1000
-1000 <= targetSum <= 1000

方法：递归

我们递归到每个叶子节点，记录根节点到当前叶子节点的路径总和，然后判断是否和target相等。

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        return reCur(root,targetSum,0);
    }

    public boolean reCur(TreeNode root, int target, int path){
        if (root!=null){
            path+=root.val;//将当前节点的值加上
            if (root.left==null && root.right==null){//当前节点为叶子节点
                if (path==target) return true;
                else return false;
            }else{//当前节点不是叶子节点，继续遍历
                return reCur(root.left,target,path)||reCur(root.right,target,path);
            }
        }else return false;
    }
}