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

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 pathSum = 0;
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *对于任意一个节点右 4 种选择
	 1.自己成一条路径，不需要左右子树
	 2.自己+左子树组成一条路径
	 3.自己+右子树组成一条路径
	 4.自己+左子树+右子树组成一条路径
	 递归终止条件为节点为 null，适用全局变量记录最大值，对于本题没有负数，默认使用第四种情况
	 
     *
     * @param root TreeNode类
     * @return int整型
     */
    public int maxMilkSum (TreeNode root) {
        dfs(root);
        return pathSum;
    }

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