15.二叉树中的最大路径和

• 2.12

  • 不需要currentSum，因为 maxL 是全局更新的，左右长度每次都选最大值（非负数）

• 1.30

  • 先算左右子树分别的最大长度（注意不能为负）
  • 尝试更新最大值（左右+跟一块加）
  • 返回根节点的值+左右其中一根最长的路径和

class Solution {
    int ans = Integer.MIN_VALUE;
    public int maxPathSum(TreeNode root) {
        sum(root);
        return ans;
    }
    public int sum(TreeNode root){
        if(root==null) return 0;
 
        int leftLength = Math.max(sum(root.left),0);
        int rigthLength = Math.max(sum(root.right),0);
 
        int maxL = root.val+leftLength+rigthLength;
        ans = Math.max(ans,maxL);
        
        return root.val+Math.max(leftLength,rigthLength);
    }
}