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

题目考察的知识点

考察对于题目的理解

题目解答方法的文字分析

首先需要明白dfs函数是获得该节点的子节点中的最大路径，获得后加上该节点的值才是通过该节点的一侧方向的最大的值，所以在访问的过程中可能会由中间节点提供这个最大路径和，所以用maxPath作为记录，递归遍历每一个节点，寻找该节点的最大路径和，最后将maxPath返回即可。

本题解析所用的编程语言

使用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整型
     */

    int maxPath = Integer.MIN_VALUE; //最大路径和 作为最终的返回值

    public int maxMilkSum (TreeNode root) { 
        // write code here
        if(root==null) return 0;
        dfs(root);
        return maxPath; //返回最大路径和
    }

    public int dfs(TreeNode root){ 
        if(root==null) return 0;
	  	// 递归判断该节点的子节点中的最大路径 
        int left = dfs(root.left); 
        int right = dfs(root.right);
        maxPath = Math.max(maxPath, left+right+root.val); //更新最大路径和 因为这个路径可能是中间节点所提供的，所以每到一个节点就需要判断maxPath是否需要更新
        return Math.max(left,right)+root.val; //加上该节点之后 返回经过该节点的最大路径和
    }
}