二叉树中的最大路径和

解题思路

分析：计算每个节点值得贡献程度，如果贡献程度小于0，则直接舍弃。计算方式可以通过计算左子树与右子树与当前节点的和的最大值，作为贡献程度。
同时 使用全局变量，每一个节点计算得到的值进行更新，获得最大的值。

代码

java

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private int value = Integer.MIN_VALUE;
    public int maxValue(TreeNode tree){
        if(tree==null){            
            return 0;
        }        
        int left = Math.max(maxValue(tree.left), 0);
        int right = Math.max(maxValue(tree.right), 0);
        int res = Math.max(left+tree.val, right+tree.val);
        value = Math.max(left+right+tree.val, value);
        return res;
    }

    public int maxPathSum(TreeNode root) {
        maxValue(root);
        return value;
    }
}