```
/**
* 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;
}
```