题解 | #二叉树中的最大路径和#

经过根节点的路径最大值 = 左子节点最大贡献 + 根节点 + 右子节点最大贡献

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);
    }
}