题解 | #农场最大产奶牛群#

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

解答方法分析：

1. 首先，定义一个结构体 TreeNode，表示二叉树节点的结构。
2. 在 Solution 类中，定义了 maxMilkSum 方法，该方法接受一个二叉树节点为参数，判断该节点是否为空，如果为空则直接返回 0。如果不为空，则初始化一个变量 maxSum，表示最大路径总和，然后调用辅助方法 maxMilk。
3. maxMilk 方法是一个递归方法，它受一个二叉树节点、当前路径的和以及 maxSum 的引用作为参数。首先判断当前节点是否为空，如果为空则返回 0。然后使用递归调用计算当前节点的左子树和右子树的最大路径和，取它们和 0 的较大值。然后计算当前节点的最大路径和为左子树最大路径和、右子树最大路径和以及当前节点值的和，并将其与 maxSum 进行比较更新。最后返回当前节点的值加左子树最大路径和和右子树最大路径和的较大值。
4. 在 main 函数中，创建一个二叉树的示例，然后创建 Solution 类的对象，调用 maxMilkSum 方法计算最大路径和，并打印输出结果。

所用编程语言：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类
     * @return int整型
     */
    int maxMilkSum(TreeNode* root) {
        if (root == nullptr) {
            return 0;
        }
        int Sum = 0;
        maxMilk(root, 0, Sum);
        return Sum;
    }
    int maxMilk(TreeNode* root, int sum, int& maxSum) {
        if (root == nullptr) {
            return 0;
        }
        int left = max(maxMilk(root->left, sum, maxSum), 0);
        int right = max(maxMilk(root->right, sum, maxSum), 0);
        int curSum = left + right + root->val;
        maxSum = max(maxSum, curSum);
        return root->val + max(left, right);
    }
};