[数据结构与算法]leetcode112 -- 路径之和Java

题目描述：


方法一：递归

• 题目其实可以看成是否存在从当前节点root到叶子节点的路径，满足其路径之和为sum
• 从根节点到当前节点的值之和为val，大 -> 小： 是否存在从当前节点的子节点到叶子的路径满足路径之和为 sum - val
• 上面很明显就可以使用到递归的性质：① 当前节点就是叶子节点，直接判断sum是否等于val即可：因为路径和已经确定了，就是当前节点的值，我们只需要判断该路径和是否满足条件即可 ② 若当前节点不是叶子节点，我们只需要递归地询问它的子节点是否满足条件即可

代码实现：

class Solution {
    public boolean hasPathSum(TreeNode root, int targetSum) {
        if (root == null){
            return false;
        }
        if (root.left == null && root.right == null){
            return targetSum == root.val;
        }
        // 递归判断当前节点的左右子节点
        return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);
    }
}

方法二：