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

大家好，我是开车的阿Q，自动驾驶的时代已经到来，没时间解释了，快和阿Q一起上车。作为自动驾驶系统工程师，必须要有最好的C++基础，让我们来一起刷题吧。

题目考察的知识点

这道题目考察了二叉树的遍历和路径求和，需要判断是否存在从任意节点到其任意子节点的路径，使得路径上节点值之和等于目标值。

题目解答方法的文字分析

我们使用递归来判断是否存在从任意节点到其任意子节点的路径，使得路径上节点值之和等于目标值。对于每个节点，如果当前节点为空，直接返回 false。如果当前节点是叶子节点，判断当前节点值是否等于目标值。否则，递归处理左子树和右子树，将目标值减去当前节点的值。此外，还需要考虑不经过当前节点的情况，即递归判断左子树和右子树是否存在路径使得节点值之和等于原始目标值。

举个例子来帮助理解：

假设有以下二叉树：

        10
       / \
      5   12
     / \
    7   3

如果目标值为 22，存在路径：10 -> 5 -> 7，路径上节点值之和等于 22，返回 true。

本题解析所用的编程语言

本题解析所用的编程语言是 C++。

完整且正确的编程代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    int originalTargetSum = 0; // 存储原始的目标值
    
    bool hasPathSumII(TreeNode* root, int targetSum) {
        if (originalTargetSum == 0) {
            originalTargetSum = targetSum; // 保存原始的目标值
        }
        
        if (!root) {
            return false; // 如果当前节点为空，直接返回false
        }
        
        if (!root->left && !root->right) {
            return root->val == targetSum; // 如果是叶子节点，判断当前节点值是否等于目标值
        }
        
        return hasPathSumII(root->left, targetSum - root->val) || hasPathSumII(root->right, targetSum - root->val)
            || hasPathSumII(root->left, originalTargetSum) || hasPathSumII(root->right, originalTargetSum);
    }
};

在这段代码中，我们使用递归来判断是否存在从任意节点到其任意子节点的路径，使得路径上节点值之和等于目标值。在递归开始时，我们将原始目标值存储起来，然后通过递归处理不同的情况。如果当前节点为空，直接返回 false。如果当前节点是叶子节点，判断当前节点值是否等于目标值。否则，递归处理左子树和右子树，将目标值减去当前节点的值。此外，还需要考虑不经过当前节点的情况，即递归判断左子树和右子树是否存在路径使得节点值之和等于原始目标值。

您的关注、点赞、收藏就是我创作的动力，三连支持阿Q！