二叉树最大路径和

给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

示例 1:

输入: [1,2,3]

       1
      / \
     2   3
输出: 6

示例 2:

输入: [-10,9,20,null,null,15,7]
   -10
   / \
  9  20
    /  \
   15   7
输出: 42

采用自下向上分析，用一个全局变量记录最大路径。
这个路径总有一个最高节点,比如示例1最高节点为1，示例2最高节点为20。
递归出口，当前节点为null，返回0；

1. 设当前节点为最高节点，计算路径和，去更新全局变量。
2. 设当前节点不是最高节点，向父节点返回当前子树的大小，取左右子树中大的那个。

class Solution {
    int max = Integer.MIN_VALUE; // 最大路径和
    public int maxPathSum(TreeNode root) {
        max(root); 
        return max;
    }
    
    // 自下向上分析
    public int max(TreeNode node){
        if(node == null) return 0; 
        
        int left = max(node.left); // 计算左子树的最大路径
        int right = max(node.right);// 计算右子树最大路径
        
        max = Math.max(max,left+node.val+right); // 设当前节点是最高节点，尝试更新全局变量
        
        return Math.max(0,Math.max(node.val+left,node.val+right));// 设当前节点不是最高节点，向父节点返回
    }   
}