# O(1) space O(n) time Simple Java solution with detail explanation

• ``````/**
* Use int[2] to maintain two possible conditions
*
* 1.         a
*         b     c
*
* 2.    a   or   a
*     b              c
*
* 3. **We have to deal with the condition where negative number occurs**
*  Negative number may exist in both of these two conditions
*
* If either of b & c or both b & c is negative, condition 1 & 2 becomes same.(Add negative number is
* the last choice for this problem **if the tree only contains negative number**
*
* If both b & c is positive, we calculate condition 1 and 2 separately. Pay attention that max[0]
* maintains the maximum value among all possible condition 1. **Rather than the current node.**
*
* The reason why we maintain two separate conditions is that
* if condition 1 gets the current maximum value, this maximum value
* can't be used for further calculation since we get a TWISTED path here,
* any parent node access to node a can only go one direction rather go either way.
*/
public int maxPathSum(TreeNode root) {

int[] max = traverse(root);

return Math.max(max[0],max[1]);
}

public int[] traverse(TreeNode root){

int[] result = {Integer.MIN_VALUE,Integer.MIN_VALUE};

if(root==null) return result;

int[] left = traverse(root.left);
int[] right = traverse(root.right);

int curMax = 0;
int pathMax = 0;
if(left[1]<0 && right[1]<0){
curMax = root.val;
pathMax = root.val;
}else if(left[1]<0 || right[1]<0){
curMax = root.val+((left[1]<0)?right[1]:left[1]);
pathMax = curMax;
}else{
curMax = root.val+left[1]+right[1];
pathMax = root.val+Math.max(left[1],right[1]);
}

result[0] = Math.max(Math.max(curMax,left[0]),right[0]);
result[1] = pathMax;

return result;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.