NC6：二叉树的最大路径和：

问题分解，求树的最大路径，递归树的节点
有三种可能：

1. 最大路径经过该节点本身从左子树到右子树
2. 最大路径经过节点本身向父节点发展
3. 最大路径就是节点本身

可以将左右边子树返回的满足情况2的最大路径和f(left)，f(right)，以及节点本身值val, 做一个组合，假设当前最大值是MAX： MAX = max(val, f(left)+val+f(right), f(left)+val, f(right)+val)
因为要满足递归条件，向上级返回的f(n)只能是情况2或者3
f(n) = max(val, f(left)+val, f(right)+val)

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {

    int MAX = Integer.MIN_VALUE;
    public int calculate(TreeNode node){
        if(node == null) return 0;
        int left = 0;
        int right = 0;
        if(node.left!=null) left = calculate(node.left);
        if(node.right!=null) right = calculate(node.right);
        int sum = node.val;
        if(left>0) sum += left;
        if(right>0) sum += right;
        MAX = Math.max(MAX, sum);
        return Math.max(node.val, Math.max(left+node.val, right+node.val));
    }
    public int maxPathSum(TreeNode root) {
        calculate(root);
        return MAX;            
    }

}