112 路径总和（递归）

1. 问题描述：

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

说明: 叶子节点是指没有子节点的节点。

示例: 
给定如下二叉树，以及目标和 sum = 22，

               5
             /   \
            4    8
           /     /  \
          11  13  4
         /   \     \
        7    2    1
返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/path-sum

2. 思路分析：

① 这道题目与是与树的路径相关的，毫无疑问使用递归来解决的，凡是遇到这种关于树中的路径相关问题都是可以使用递归来求解，因为求解的是树中从根节点到叶子节点之间的路径是否存在目标值，所以我们可以写一个有返回值的递归，里面传入一个参数用来记录从当前节点往下递归的时候累加到上一个节点的路径总和，使用这个变量来记录很方便地进行路径总和的判断所以当到达了叶子节点的时候我们可以判断出累加到叶子节点路径总和是否等于了目标值，假如等于了直接返回true

② 因为一开始在方法中传入的是0，而在递归中我们记录的是累加到上一个节点的值，所以当到达了叶子节点的值之后那么我们需要加上最后一个叶子节点的值，这样才是从根节点到叶子节点的路径值，这个可以结合具体的例子理解一下，并且我们假如发现存在一条路径的值等于了目标值之后可以直接返回true，所以有返回值的递归比无返回值的递归效率更高，因为发现一个满足条件会层层返回true，无需进行其他路径的搜索了，所以来说执行的时间会短很多，这个特点有之前领扣中的79 单词搜索、1367 二叉树中的列表特点是很像的，直接返回true

③ 我在递归的出口尝试一下剪枝，当发现中间过程的值大于了目标值之后直接返回false，其实这个是不对的，因为有可能存在负值的情况不能够这样来剪枝，进行比对的时候一定要到叶子节点的值才能够进行比对

3. 代码如下：

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

    public boolean dfs(TreeNode root, int sum, int cur) {
        if (root == null)  return false;
        /*因为在递归的过程中加上的是上一个节点的值所以在最后叶子节点判断时候需要加上叶子节点的值*/
        if (root.left == null && root.right == null && sum == cur + root.val)  return true;
        /*发现一个为true了那么直接返回即可*/
        boolean l = dfs(root.left, sum, cur + root.val);
        if (l) return true;
        boolean r = dfs(root.right, sum, cur + root.val);
        if (r) return true;
        return false;
    }
}