refactor 105

fishercoder1534 · fishercoder1534 · commit 8014ff08cc87 · 2021-10-26T21:58:39.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_105.java b/src/main/java/com/fishercoder/solutions/_105.java
@@ -12,6 +12,10 @@ public static class Solution1 {
          * credit: https://discuss.leetcode.com/topic/29838/5ms-java-clean-solution-with-caching use
          * HashMap as the cache so that accessing inorder index becomes O(1) time Note: The first
          * element of preorder array is the root!
+         *
+         * Using a pen and paper to visualize this helps a great deal!
+         * preorder array has the root at the head, then we could use this number as a pivot in the inorder array: all elements on the left of this pivot should form a left subtree of this pivot
+         * and anything on the right side of this pivot in the inorder array should form a right subtree of this pivot.
          */
         public TreeNode buildTree(int[] preorder, int[] inorder) {
             Map<Integer, Integer> inorderMap = new HashMap();
@@ -23,14 +27,14 @@ public TreeNode buildTree(int[] preorder, int[] inorder) {
             return buildTree(preorder, 0, preorder.length - 1, inorderMap, 0, inorder.length - 1);
         }
 
-        private TreeNode buildTree(int[] preorder, int preStart, int preEnd,
-                                   Map<Integer, Integer> inorderMap, int inStart, int inEnd) {
+        private TreeNode buildTree(int[] preorder, int preStart, int preEnd, Map<Integer, Integer> inorderMap, int inStart, int inEnd) {
             if (preStart > preEnd || inStart > inEnd) {
                 return null;
             }
 
             TreeNode root = new TreeNode(preorder[preStart]);
             int inRoot = inorderMap.get(preorder[preStart]);
+            //This line is the key to figure out how many nodes should be on the left subtree
             int numsLeft = inRoot - inStart;
 
             /**It's easy to understand and remember:
diff --git a/src/test/java/com/fishercoder/_105Test.java b/src/test/java/com/fishercoder/_105Test.java
@@ -3,39 +3,60 @@
 import com.fishercoder.common.classes.TreeNode;
 import com.fishercoder.common.utils.TreeUtils;
 import com.fishercoder.solutions._105;
+
 import java.util.Arrays;
+
 import org.junit.BeforeClass;
 import org.junit.Test;
 
 import static junit.framework.Assert.assertEquals;
 
 public class _105Test {
-  private static _105.Solution1 solution1;
-  private static TreeNode expected;
-  private static TreeNode actual;
-  private static int[] preorder;
-  private static int[] inorder;
-
-  @BeforeClass
-  public static void setup() {
-    solution1 = new _105.Solution1();
-  }
-
-  @Test
-  public void test1() {
-    preorder = new int[] {1, 2, 3};
-    inorder = new int[] {2, 1, 3};
-    actual = solution1.buildTree(preorder, inorder);
-    expected = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3));
-    assertEquals(expected, actual);
-  }
-
-  @Test
-  public void test2() {
-    preorder = new int[] {1, 2, 4, 5, 3};
-    inorder = new int[] {4, 2, 5, 1, 3};
-    actual = solution1.buildTree(preorder, inorder);
-    expected = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, 4, 5));
-    assertEquals(expected, actual);
-  }
+    private static _105.Solution1 solution1;
+    private static TreeNode expected;
+    private static TreeNode actual;
+    private static int[] preorder;
+    private static int[] inorder;
+
+    @BeforeClass
+    public static void setup() {
+        solution1 = new _105.Solution1();
+    }
+
+    @Test
+    public void test1() {
+        preorder = new int[]{1, 2, 3};
+        inorder = new int[]{2, 1, 3};
+        actual = solution1.buildTree(preorder, inorder);
+        expected = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3));
+        assertEquals(expected, actual);
+    }
+
+    @Test
+    public void test2() {
+        preorder = new int[]{1, 2, 4, 5, 3};
+        inorder = new int[]{4, 2, 5, 1, 3};
+        actual = solution1.buildTree(preorder, inorder);
+        expected = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, 4, 5));
+        assertEquals(expected, actual);
+    }
+
+    @Test
+    public void test3() {
+        preorder = new int[]{3, 9, 20, 15, 7};
+        inorder = new int[]{9, 3, 15, 20, 7};
+        actual = solution1.buildTree(preorder, inorder);
+        expected = TreeUtils.constructBinaryTree(Arrays.asList(3, 9, 20, null, null, 15, 7));
+        assertEquals(expected, actual);
+    }
+
+    @Test
+    public void test4() {
+        preorder = new int[]{3, 1, 2, 4};
+        inorder = new int[]{1, 2, 3, 4};
+        actual = solution1.buildTree(preorder, inorder);
+        expected = TreeUtils.constructBinaryTree(Arrays.asList(3, 1, 4, null, 2));
+        TreeUtils.printBinaryTree(expected);
+        assertEquals(expected, actual);
+    }
 }
