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

考察知识点：二叉树、后序遍历、递归

解题思路：这道题主要考察的是二叉树的后序遍历。具体解法为：使用全局变量`max`存储最终求得总和的结果，然后再采用后续遍历依次求得左右子树的最大单支总和，左单支总和 + 右单支总和 + 当前节点值就是当前节点所能够拿到的最大总和，然后与`max`比较并更新`max`，最后遍历结束，`max`也就变成了整棵树的最大总和

本题解所用语言：java

具体代码如下：

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 {
    int max = 0;
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param root TreeNode类
     * @return int整型
     */
    public int maxMilkSum (TreeNode root) {
        // write code here
        maxSum(root);
        return max;
    }

    public int maxSum(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = maxSum(root.left);
        int right = maxSum(root.right);

        int sum = left + right + root.val;
        if (sum > max) {
            max = sum;
        }

        return Math.max(left, right) + root.val;
    }

}