Serena211
diff --git a/‎bin/Class22_Advanced4/MaximumPathSumBinaryTree2.class‎
475 Bytes b/‎bin/Class22_Advanced4/MaximumPathSumBinaryTree2.class‎
475 Bytes
diff --git a/‎bin/Class22_Advanced4/MaximumPathSumBinaryTree3.class‎
0 Bytes b/‎bin/Class22_Advanced4/MaximumPathSumBinaryTree3.class‎
0 Bytes
diff --git a/‎src/Class22_Advanced4/MaximumPathSumBinaryTree2.java‎
Lines changed: 22 additions & 1 deletion b/‎src/Class22_Advanced4/MaximumPathSumBinaryTree2.java‎
Lines changed: 22 additions & 1 deletion
diff --git a/‎src/Class22_Advanced4/MaximumPathSumBinaryTree3.java‎
Lines changed: 0 additions & 1 deletion b/‎src/Class22_Advanced4/MaximumPathSumBinaryTree3.java‎
Lines changed: 0 additions & 1 deletion
@@ -13,7 +13,28 @@
 public class MaximumPathSumBinaryTree2 {
 	public int maxPathSum(TreeNode root) {
 		int[] max = new int[]{Integer.MIN_VALUE};
-		return 0;
+		if (root == null) {
+			return Integer.MIN_VALUE;
+		} else {
+			max[0] = root.val;
+		}
+		helper(root, max);
+		return max[0];
+	}
+
+	private int helper(TreeNode root, int[] max) {
+		// TODO Auto-generated method stub
+		if (root == null) {
+			return 0;
+		}
+		int left = helper(root.left, max);
+		int right = helper(root.right, max);
+		
+		// largest subArray sum: dp_class15
+		left = left < 0 ? 0 : left;			// check left path sum. if sum < 0, then don't add it on root
+		right = right < 0? 0 : right;		// check right path sum as above
+		max[0] = Math.max(max[0], root.val + left + right);	//if left == 0 && right == 0, current max == root.val
+		return root.val + Math.max(left, right);	// return largest sum path.
 	}
 
 	public static void main(String[] args) {
 
@@ -34,7 +34,6 @@ private int helper(TreeNode root, int[] max) {
 
 		max[0] = Math.max(Math.max(left, right) + root.val, max[0]);
 		return root.val + Math.max(left, right);
-		
 	}
 
 	public static void main(String[] args) {
Original file line number	Diff line number	Diff line change
`@@ -34,7 +34,6 @@ private int helper(TreeNode root, int[] max) {`
`34`	`34`
`35`	`35`	`max[0] = Math.max(Math.max(left, right) + root.val, max[0]);`
`36`	`36`	`return root.val + Math.max(left, right);`
`37`		`-`
`38`	`37`	`}`
`39`	`38`
`40`	`39`	`public static void main(String[] args) {`