124.Binary Tree Maximum Path Sum

Solution 1: accepted 4ms

Time: O(n)
Space: O(1) (O(h) if the stack space is considered)

```java
class Solution {
// consider to use a class Type to record the value
static int max = Integer.MIN_VALUE;
public int maxPathSum(TreeNode root) {
maxPath(root);
int temp = max;
max = Integer.MIN_VALUE;
return temp;
}

public int maxPath(TreeNode root) {
    if (root == null) {
        return 0;
    } else {
        // divide
        int left = maxPath(root.left);
        int right = maxPath(root.right);

        // conquer
        max = Math.max(max, root.val + left + right);
        return Math.max(0, root.val + Math.max(0, Math.max(left, right)));
    }       
}

}