package com.fishercoder.solutions;

import com.fishercoder.common.classes.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * 124. Binary Tree Maximum Path Sum
 * 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 {

    public static class Solution1 {
        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);
        }
    }

    public static class Solution2 {
        /**This one uses a map to cache, but surprisingly, it's 10% slower than all submissions compared with solution1*/
        int max = Integer.MIN_VALUE;

        public int maxPathSum(TreeNode root) {
            Map<TreeNode, Integer> map = new HashMap<>();
            dfs(root, map);
            return max;
        }

        private int dfs(TreeNode root, Map<TreeNode, Integer> map) {
            if (root == null) {
                return 0;
            }
            if (map.containsKey(root)) {
                return map.get(root);
            }
            int left = Math.max(0, dfs(root.left, map));
            int right = Math.max(0, dfs(root.right, map));
            max = Math.max(max, root.val + left + right);
            int pathSum = root.val + Math.max(left, right);
            map.put(root, pathSum);
            return pathSum;
        }
    }
}

@@ -168,18 +168,17 @@
 ath Sum%0A
- *
+%0A
  Given a
@@ -218,18 +218,16 @@
 th sum.%0A
- *
  For thi
@@ -316,18 +316,16 @@
 ny node%0A
- *
  in the 
@@ -550,18 +550,16 @@
 _124 %7B%0A%0A
-  
   public
@@ -584,28 +584,24 @@
 tion1 %7B%0A    
-  
-  
 int max = In
@@ -614,36 +614,32 @@
 MIN_VALUE;%0A%0A    
- 
-   
 public int maxPa
@@ -657,30 +657,24 @@
 ode root) %7B%0A
-      
       dfs(ro
@@ -676,38 +676,32 @@
 fs(root);%0A      
-     
- 
 return max;%0A    
@@ -696,35 +696,27 @@
 rn max;%0A    
-    %7D%0A%0A    
+%7D%0A%0A
     private 
@@ -738,38 +738,32 @@
 e root) %7B%0A      
-     
- 
 if (root == null
@@ -762,32 +762,24 @@
  == null) %7B%0A
-        
         retu
@@ -790,31 +790,19 @@
 ;%0A      
-     
- 
 %7D%0A%0A
-      
       in
@@ -839,22 +839,16 @@
 t), 0);%0A
-      
       in
@@ -890,30 +890,24 @@
  0);%0A%0A      
- 
-     
 max = Math.m
@@ -943,30 +943,24 @@
 ht);%0A%0A      
-  
-    
 return root.
@@ -996,23 +996,15 @@
     
-   
- 
 %7D%0A
-  
   %7D%0A%0A
-  
   pu
@@ -1041,15 +1041,19 @@
     
+/**%0A
     
-/**
+ * 
 This
@@ -1141,16 +1141,23 @@
 compared
+%0A     *
  with so
@@ -1167,15 +1167,17 @@
 ion1
-*/
 %0A    
+ */%0A
     
@@ -1210,20 +1210,16 @@
 E;%0A%0A    
- 
-   
 public i
@@ -1255,22 +1255,16 @@
 %7B%0A      
-    
-  
 Map%3CTree
@@ -1307,22 +1307,16 @@
 ;%0A      
-     
- 
 dfs(root
@@ -1323,22 +1323,16 @@
 , map);%0A
-      
       re
@@ -1349,23 +1349,15 @@
     
-    %7D%0A%0A   
+%7D%0A%0A
     
- 
 priv
@@ -1409,30 +1409,24 @@
 ger%3E map) %7B%0A
-      
       if (ro
@@ -1443,32 +1443,24 @@
 ) %7B%0A        
-       
- 
 return 0;%0A  
@@ -1459,38 +1459,26 @@
 rn 0;%0A      
-      %7D%0A      
+%7D%0A
       if (ma
@@ -1504,32 +1504,24 @@
 ) %7B%0A        
- 
-       
 return map.g
@@ -1526,30 +1526,24 @@
 .get(root);%0A
-      
       %7D%0A    
@@ -1540,30 +1540,24 @@
     %7D%0A      
- 
-     
 int left = M
@@ -1591,30 +1591,24 @@
 ap));%0A      
-  
-    
 int right = 
@@ -1648,22 +1648,16 @@
 ;%0A      
-   
-   
 max = Ma
@@ -1700,22 +1700,16 @@
 ;%0A      
-    
-  
 int path
@@ -1754,22 +1754,16 @@
 ;%0A      
-     
- 
 map.put(
@@ -1778,22 +1778,16 @@
 thSum);%0A
-      
       re
@@ -1804,22 +1804,16 @@
 um;%0A    
-    %7D%0A  
+%7D%0A
   %7D%0A%7D%0A

refactor 124