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

1. 题目考察的知识点

二叉树的遍历

2. 题目解答方法的文字分析

对于二叉树中的一个节点，该节点的最大路径和取决于该节点的值与该节点的左右子节点的单向的最大路径和，如果子节点单向的最大路径和为正，则计入该节点的最大路径和，否则不计入该节点的最大路径和。维护一个全局变量 maxSum 存储最大路径和，在递归过程中更新 maxSum 的值，最后得到的 maxSum 的值即为二叉树中的最大路径和。

3. 本题解析所用的编程语言

java

4. 完整且正确的编程代码

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整型
     */
     int maxSum = Integer.MIN_VALUE;
    public int maxMilkSum (TreeNode root) {
        dfs(root);
        return maxSum;
    }
    public int dfs(TreeNode node) {
        if (node == null) {
            return 0;
        }
        
        int left = Math.max(dfs(node.left), 0);
        int right = Math.max(dfs(node.right), 0);

        int priceNewpath = node.val + left + right;

        maxSum = Math.max(maxSum, priceNewpath);

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