Java 题解 | #牛的奶量统计II#

本题所用的编程语言为 Java

考察的主要知识点有：

1. 二叉树（Binary Tree）：二叉树是一种特殊的树结构，其中每个节点最多有两个子节点。二叉树可以为空树（没有节点），也可以是非空树，其中一个节点作为根节点，其余节点分别形成根节点的左子树和右子树。
2. 递归（Recursion）：递归是一种解决问题的方法，通过将问题分解为更小、相似的子问题来求解。在树的问题中，递归常常用于遍历树的节点或者对每个节点进行操作。
3. 路径和（Path Sum）：指从根节点到叶子节点的路径上所有节点值的总和。题目要求判断是否存在一条路径的节点值之和等于给定的目标和。

代码的解释大纲如下：

1. 创建一个类 Solution。
2. 定义一个内部类 TreeNode，表示二叉树的节点，包含一个整数值 val 和两个子节点 left 和 right。
3. 在 Solution 类中定义一个方法 pathSumFrom，用于判断从给定节点出发是否存在一条路径，使得路径上节点值之和等于给定的目标和。
4. 如果当前节点为空，则返回 false。
5. 如果当前节点为叶子节点（即左右子节点都为空），则判断当前节点的值是否等于目标和，如果相等，则返回 true，否则返回 false。
6. 递归调用 pathSumFrom 方法判断当前节点的左子节点和右子节点中是否存在满足条件的路径，只要左子节点或右子节点中存在满足条件的路径，就返回 true。
7. 在 Solution 类中定义另一个方法 hasPathSumII，用于判断是否存在一条路径的节点值之和等于给定的目标和。该方法通过递归调用 pathSumFrom 方法判断根节点和其左右子节点中是否存在满足条件的路径。
8. 如果根节点为空，则返回 false。
9. 如果根节点不为空，则递归调用 pathSumFrom 方法判断根节点和其左右子节点中是否存在满足条件的路径，只要其中一条路径存在，就返回 true。
10. 如果遍历完整棵二叉树都没有找到满足条件的路径，最终返回 false。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param targetSum int整型
     * @return bool布尔型
     */
    public boolean pathSumFrom(TreeNode node, int sum) {
        if (node == null) {
            return false;
        }
        if (node.left == null && node.right == null) {
            return node.val == sum;
        }
        return pathSumFrom(node.left, sum - node.val) ||
               pathSumFrom(node.right, sum - node.val);
    }

    public boolean hasPathSumII(TreeNode root, int targetSum) {
        if (root == null) {
            return false;
        }
        return pathSumFrom(root, targetSum) || hasPathSumII(root.left, targetSum) ||
               hasPathSumII(root.right, targetSum);
    }
}