@@ -0,0 +1,1390 @@
+package leetcode.binary_tree_maximum_path_sum;%0A%0Aimport common.TreeNode;%0A%0Apublic class Solution %7B%0A%09boolean allNegative;%0A%09int maxVal;%0A%09%0A%09public int maxPathSum(TreeNode root) %7B%0A%09%09allNegative = true;%0A%09%09maxVal = root.val;%0A%09%09int ans = maxPathSum2(root).allMax;%0A%09%09if(allNegative)%7B%0A%09%09%09return maxVal;%0A%09%09%7Delse%7B%0A%09%09%09return ans;%0A%09%09%7D%0A%09%7D%0A%09%0A%09public RetVal maxPathSum2(TreeNode cur)%7B%0A%09%09if(cur == null)%7B%0A%09%09%09return new RetVal(0, 0);%0A%09%09%7D%0A%09%09if(cur.val %3E= 0) allNegative = false;%0A%09%09if(cur.val %3E maxVal) maxVal = cur.val;%0A%09%09RetVal ret;%0A%09%09if(cur.val %3C 0)%0A%09%09%09ret = new RetVal(0, 0);%0A%09%09else%0A%09%09%09ret = new RetVal(cur.val, cur.val);%0A%09%09RetVal left = maxPathSum2(cur.left);%0A%09%09RetVal right = maxPathSum2(cur.right);%0A%09%09if(ret.endAtRoot %3C left.endAtRoot + cur.val)%7B%0A%09%09%09ret.endAtRoot = left.endAtRoot + cur.val;%0A%09%09%7D%0A%09%09if(ret.endAtRoot %3C right.endAtRoot + cur.val)%7B%0A%09%09%09ret.endAtRoot = right.endAtRoot + cur.val;%0A%09%09%7D%0A%09%09if(ret.allMax %3C left.allMax)%7B%0A%09%09%09ret.allMax = left.allMax;%0A%09%09%7D%0A%09%09if(ret.allMax %3C right.allMax)%7B%0A%09%09%09ret.allMax = right.allMax;%0A%09%09%7D%0A%09%09if(ret.allMax %3C right.endAtRoot + cur.val + left.endAtRoot)%7B%0A%09%09%09ret.allMax = right.endAtRoot + cur.val + left.endAtRoot;%0A%09%09%7D%0A%09%09if(ret.allMax %3C ret.endAtRoot)%7B%0A%09%09%09ret.allMax = ret.endAtRoot;%0A%09%09%7D%0A%09%09return ret;%0A%09%09%0A%09%7D%0A%09%0A%09public class RetVal%7B%0A%09%09int endAtRoot;%0A%09%09int allMax;%0A%09%09public RetVal(int passRoot, int allMax)%7B%0A%09%09%09this.endAtRoot = passRoot;%0A%09%09%09this.allMax = allMax;%0A%09%09%7D%0A%09%7D%0A%7D%0A

Add java solution for 124. Binary Tree Maximum Path Sum