add a solution for 106

fishercoder1534 · fishercoder1534 · commit a2146762bb9c · 2021-10-27T08:32:54.000-07:00
diff --git a/src/main/java/com/fishercoder/solutions/_106.java b/src/main/java/com/fishercoder/solutions/_106.java
@@ -56,4 +56,31 @@ private TreeNode buildTreeRecursively(Map<Integer, Integer> inorderMap, int inor
             return root;
         }
     }
+
+    public static class Solution2 {
+        /**
+         * My own solution after inspiration from LeetCode 105.
+         * I go from the right to the left for the postorder array, also, I build the tree by forming the right subtree first and then the left subtree.
+         * A bit different from using numsLeft from LeetCode 106, I use numsRight, meaning the number of nodes needed to form the right subtree in the inorder array.
+         */
+        public TreeNode buildTree(int[] inorder, int[] postorder) {
+            Map<Integer, Integer> inMap = new HashMap<>();
+            for (int i = 0; i < inorder.length; i++) {
+                inMap.put(inorder[i], i);
+            }
+            return helper(postorder, inorder, inMap, postorder.length - 1, 0, 0, inorder.length - 1);
+        }
+
+        private TreeNode helper(int[] postorder, int[] inorder, Map<Integer, Integer> inMap, int postStart, int postEnd, int inStart, int inEnd) {
+            if (postStart < postEnd) {
+                return null;
+            }
+            int inRoot = inMap.get(postorder[postStart]);
+            int numsRight = inEnd - inRoot;
+            TreeNode node = new TreeNode(postorder[postStart]);
+            node.right = helper(postorder, inorder, inMap, postStart - 1, postStart - numsRight, inRoot + 1, inEnd);
+            node.left = helper(postorder, inorder, inMap, postStart - numsRight - 1, postEnd, inStart, inRoot - 1);
+            return node;
+        }
+    }
 }
diff --git a/src/test/java/com/fishercoder/_106Test.java b/src/test/java/com/fishercoder/_106Test.java
@@ -12,6 +12,7 @@
 
 public class _106Test {
     private static _106.Solution1 solution1;
+    private static _106.Solution2 solution2;
     private static TreeNode expected;
     private static TreeNode actual;
     private static int[] inorder;
@@ -20,6 +21,7 @@ public class _106Test {
     @BeforeClass
     public static void setup() {
         solution1 = new _106.Solution1();
+        solution2 = new _106.Solution2();
     }
 
     @Test
@@ -36,6 +38,8 @@ public void test1() {
         actual = solution1.buildTree(inorder, postorder);
         expected = TreeUtils.constructBinaryTree(Arrays.asList(3, 1, null, null, 2));
         assertEquals(expected, actual);
+        actual = solution2.buildTree(inorder, postorder);
+        assertEquals(expected, actual);
     }
 
     @Test
@@ -52,7 +56,7 @@ public void test2() {
          *  4
          */
         postorder = new int[]{4, 2, 5, 1, 3};
-        inorder  = new int[]{1, 2, 4, 5, 3};
+        inorder = new int[]{1, 2, 4, 5, 3};
         actual = solution1.buildTree(inorder, postorder);
         expected = TreeUtils.constructBinaryTree(Arrays.asList(3, 1, null, null, 5, 2, null, null, 4));
         assertEquals(expected, actual);
