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

考察的知识点：二叉树的递归遍历；

解答方法分析：

1. 判断根节点是否为空，如果为空则直接返回false。
2. 调用辅助函数helper，传入根节点、目标值和路径和初始化为0，判断当前节点是否满足路径和等于目标值的条件。
3. 如果辅助函数返回true，则表示存在一条路径使得路径上的节点值之和等于目标值，直接返回true。
4. 否则，继续递归调用hasPathSumII函数，传入左子树和右子树，并判断是否存在满足条件的路径。
5. 如果左子树或右子树中存在满足条件的路径，则返回true；否则返回false。

所用编程语言：C++；

完整编程代码：↓

/**
 * struct TreeNode {
 *  int val;
 *  struct TreeNode *left;
 *  struct TreeNode *right;
 *  TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @param targetSum int整型
     * @return bool布尔型
     */

    bool hasPathSumII(TreeNode* root, int targetSum) {
        if (root == nullptr) {
            return false;
        }
        return helper(root, targetSum, 0) || hasPathSumII(root->left,targetSum) || hasPathSumII(root->right,targetSum);
    }

    bool helper(TreeNode* node, int target, int pathSum) {
        if (node == nullptr) {
            return false;
        }

        pathSum += node->val;

        if (node->left == nullptr && node->right == nullptr && pathSum == target) {
            return true;
        }

        return helper(node->left, target, pathSum) ||
               helper(node->right, target, pathSum);
    }
};