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

知识点：递归

思路：稍微思考一下就知道，其实就左子树路径最大和和右子树路径最大和加上根节点

左子树最大路径和，求和思路：就和找最大叶节点一样，只是这次是累加起来

第二版：之前思路错了，根节点不一定必须要走过，如果子节点有更大的路径的话

其实任何一个节点都有可能，比如一颗树最后的一颗子树上是 1 1000 1000，那么

选取最大路径的话，只能是走这一条路

那么在我第一版的数据结构上加一个遍历就行了，每棵root都给与尊重

总结：这题就是求叶子最大值的一个变式，对于我解题的思路来说。

那么时间复杂度是O(logn) 2

编程语言：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 getMaxPath(TreeNode root){
        if(root == null)
            return 0;
        int sum = root.val;
        sum = sum + Math.max(getMaxPath(root.left),getMaxPath(root.right));
        return sum;
    }

    /**
     * 其实就是求最大值的一个变式
     * @param root
     * @return
     */
    public int maxMilkSum (TreeNode root) {
        // write code here
        if(root == null)
            return 0;
        //前置处理
        //当前这个节点的最大路径值，类比max = root.val
        int max = getMaxPath(root.left) + getMaxPath(root.right) + root.val;

        //每一个root都给予尊重，对每个根节点都进行一次getMaxPath
        //将当前节点的max和左、右分别进行对比
        max = Math.max(max,maxMilkSum(root.left));
        max = Math.max(max,maxMilkSum(root.right));

        //后置处理
        //和求最大值一样，返回处理后的值
        return max;
    }
}