题解 | #农场最大产奶牛群#
农场最大产奶牛群
https://www.nowcoder.com/practice/16d827f124e14e05b988f3002e7cd651
本题知识点分析: 二叉树遍历、深度优先搜索
本题解题思路分析:
利用深度优先算法寻找左子树和右子树的路径和
记录最大路径与每次选择左右子树中较大值+root.val当前节点值比较
本题使用编程语言: 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 {
private int maxMilk = 0;
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param root TreeNode类
* @return int整型
*/
public int maxMilkSum (TreeNode root) {
// write code here
traverse(root);
return maxMilk;
}
private int traverse(TreeNode root){
if(root == null) return 0;
int left = traverse(root.left);
int right = traverse(root.right);
int path = left + root.val + right;
maxMilk = Math.max(maxMilk,path);
return Math.max(left,right) + root.val;
}
}