经过根节点的路径最大值 = 左子节点最大贡献 + 根节点 + 右子节点最大贡献
priceNewPath 记录最大路径和
递归计算每个节点的最大贡献值 一个节点最大贡献值 = 自己 + 左子节点和右子节点的较大者
nodeGain = node.val + Math.Max(leftgain,rightgain);
当节点的贡献值小于0 那么舍去 该节点贡献值就为0
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类
* @return int整型
*/
public int maxPathSum (TreeNode root) {
// write code here
if (root == null){
return 0;
}
getGain(root);
return maxSum;
}
int maxSum = Integer.MIN_VALUE;
//
public int getGain(TreeNode root){
if(root == null){
return 0;
}
int leftChildGain = Math.max(getGain(root.left),0);
int rightChildGain = Math.max(getGain(root.right),0);
int newPathSum = root.val + leftChildGain + rightChildGain;
maxSum = Math.max(newPathSum,maxSum);
return root.val + Math.max(leftChildGain,rightChildGain);
}
}