refactor 124

fishercoder1534 · fishercoder1534 · commit b0923fd0cc3d · 2018-04-09T07:32:40.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_124.java b/src/main/java/com/fishercoder/solutions/_124.java
@@ -7,9 +7,10 @@
 
 /**
  * 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.
+
+ 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.
 
@@ -24,51 +25,54 @@
  */
 public class _124 {
 
-    public static class Solution1 {
-        int max = Integer.MIN_VALUE;
+  public static class Solution1 {
+    int max = Integer.MIN_VALUE;
 
-        public int maxPathSum(TreeNode root) {
-            dfs(root);
-            return max;
-        }
+    public int maxPathSum(TreeNode root) {
+      dfs(root);
+      return max;
+    }
 
-        private int dfs(TreeNode root) {
-            if (root == null) {
-                return 0;
-            }
+    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);
+      int left = Math.max(dfs(root.left), 0);
+      int right = Math.max(dfs(root.right), 0);
 
-            max = Math.max(max, root.val + left + right);
+      max = Math.max(max, root.val + left + right);
 
-            return root.val + Math.max(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;
     }
 
-    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;
-        }
+    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;
     }
+  }
 }
