475.Binary Tree Maximum Path Sum II

1.Description(Medium)

Given a binary tree, find the maximum path sum from root.

The path may end at any node in the tree and contain at least one node in it.

Example

Given the below binary tree:

  1
 / \
2   3

return4. (1->3)

2.Code

判断left 和right的正负，全负就只返回root.val,一方负就返回另一方+root.val，全正就取max(left,right)+root.val

public int maxPathSum2(TreeNode root) {
        if(root==null){
         return Integer.MIN_VALUE;
     }
     int left=maxPathSum2(root.left);
     int right=maxPathSum2(root.right);

     if(left<0 && right<0){
         return root.val;
     }
     if(left<0){
         return right+root.val;
     }
     if(right<0){
         return left+root.val;
     }
     return Math.max(left,right)+root.val;
}