package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

/**
 * Given a binary tree, find the maximum path sum.

 For this problem, a path is defined as any sequence of nodes from some starting node to any node
 in the tree along the parent-child connections.

 The path must contain at least one node and does not need to go through the root.

 For example:
 Given the below binary tree,

   1
  / \
 2   3

 Return 6.
 */
public class _124 {

    int max = Integer.MIN_VALUE;

    public int maxPathSum(TreeNode root) {
        dfs(root);
        return max;
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }

        int left = Math.max(dfs(root.left), 0);
        int right = Math.max(dfs(root.right), 0);

        max = Math.max(max, root.val + left + right);

        return root.val + Math.max(left, right);
    }

}

@@ -82,11 +82,97 @@
 e;%0A%0A
-/**
+import java.util.HashMap;%0Aimport java.util.Map;%0A%0A/**%0A * 124. Binary Tree Maximum Path Sum
 %0A * 
@@ -219,17 +219,18 @@
 th sum.%0A
-%0A
+ *
  For thi
@@ -319,16 +319,18 @@
 ny node%0A
+ *
  in the 
@@ -555,16 +555,56 @@
 _124 %7B%0A%0A
+    public static class Solution1 %7B%0A    
     int 
@@ -629,16 +629,20 @@
 VALUE;%0A%0A
+    
     publ
@@ -684,16 +684,20 @@
         
+   
+ 
 dfs(root
@@ -695,24 +695,28 @@
  dfs(root);%0A
+    
         retu
@@ -723,23 +723,31 @@
 rn max;%0A
+    
     %7D%0A%0A
+    
     priv
@@ -783,16 +783,20 @@
         
+    
 if (root
@@ -815,24 +815,28 @@
             
+ 
+   
 return 0;%0A  
@@ -833,32 +833,36 @@
 turn 0;%0A        
+    
 %7D%0A%0A        int l
@@ -852,24 +852,28 @@
  %7D%0A%0A        
+  
+  
 int left = M
@@ -900,16 +900,20 @@
 t), 0);%0A
+    
         
@@ -963,16 +963,20 @@
         
+  
+  
 max = Ma
@@ -1018,24 +1018,28 @@
 );%0A%0A        
+    
 return root.
@@ -1071,13 +1071,935 @@
 t);%0A    
+   
+ 
 %7D%0A
+    %7D%0A%0A    public static class Solution2 %7B%0A        /**This one uses a map to cache, but surprisingly, it's 10%25 slower than all submissions compared with solution1*/%0A        int max = Integer.MIN_VALUE;%0A%0A        public int maxPathSum(TreeNode root) %7B%0A            Map%3CTreeNode, Integer%3E map = new HashMap%3C%3E();%0A            dfs(root, map);%0A            return max;%0A        %7D%0A%0A        private int dfs(TreeNode root, Map%3CTreeNode, Integer%3E map) %7B%0A            if (root == null) %7B%0A                return 0;%0A            %7D%0A            if (map.containsKey(root)) %7B%0A                return map.get(root);%0A            %7D%0A            int left = Math.max(0, dfs(root.left, map));%0A            int right = Math.max(0, dfs(root.right, map));%0A            max = Math.max(max, root.val + left + right);%0A            int pathSum = root.val + Math.max(left, right);%0A            map.put(root, pathSum);%0A            return pathSum;%0A        %7D%0A    %7D
 %0A%7D%0A

refactor 124