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

知识点：二叉树，递归

题目要求找到一个最大的路径和，可以由任意节点到达叶子节点，题目并没有要求只能向下寻找叶子节点，也就是最大的路径和，一定是一个叶子节点向上累加，再向下累加到另一个叶子节点，这样才能保证路径和一定是最大的，所以，我们应该寻找每一个节点所能到达的最大的左右叶子节点，也就是将当前节点作为根节点，寻找左右两个到达叶子节点的最大路径，当前节点与二者相加即为当前路径最大和。

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

    private int getSum(TreeNode root) {
        if(root == null) {
            return 0;
        }
        return root.val + Math.max(getSum(root.left), getSum(root.right));
    }
}