算法：二叉树的最大路径和

leetcode 124 二叉树的最大路径和

例：
10
/ \
-1 20
最大的路径和为 30,。
这里提出一个贡献值的概念。
如果一个节点是叶子节点 则 贡献值为自己
如果一个节点非节点则贡献值为 当前值 + 子节点的贡献值
则如果一个节点的贡献值为正，则它有可能加入路径中！也有可能不加入，我们需要维护一个当前的最大值。不断的更新。如果一个节点贡献值为负值，则它必定不加入最大值。 我们可以使用max(0,value)来排除这个节点
代码实现

public class MaxPathSum {


   //维护一个最大路径
    private int max;


    private int max(TreeNode root){
        if (root == null)
            return 0;

        //left的贡献值，这里用0可以排除一些负数
        int left = Math.max(max(root.left),0);
        //right的贡献值
        int right = Math.max(max(root.right),0); 
       //更新这个子树的路径
        max = Math.max(left + right + root.val,max);
        //返回这棵树的贡献值
        return root.val + Math.max(left,right);
    }
    public int maxPathSum(TreeNode root) {
        max(root);
        return max;
    }

}