Skip to content

Commit d15b618

Browse files
fishercoder1534fishercoder1534
committed
refactor 105
1 parent ad5b061 commit d15b618

File tree

2 files changed

+61
-66
lines changed

2 files changed

+61
-66
lines changed

‎src/main/java/com/fishercoder/solutions/_105.java

Lines changed: 34 additions & 32 deletions
Original file line numberDiff line numberDiff line change
@@ -14,40 +14,42 @@
1414
*/
1515
public class _105 {
1616

17-
/**
18-
* credit: https://discuss.leetcode.com/topic/29838/5ms-java-clean-solution-with-caching
19-
* use HashMap as the cache so that accessing inorder index becomes O(1) time
20-
* Note: The first element of preorder array is the root!
21-
*/
22-
public TreeNode buildTree(int[] preorder, int[] inorder) {
23-
Map<Integer, Integer> inorderMap = new HashMap();
24-
for (int i = 0; i < inorder.length; i++) {
25-
inorderMap.put(inorder[i], i);
17+
public static class Solution1 {
18+
/**
19+
* credit: https://discuss.leetcode.com/topic/29838/5ms-java-clean-solution-with-caching use
20+
* HashMap as the cache so that accessing inorder index becomes O(1) time Note: The first
21+
* element of preorder array is the root!
22+
*/
23+
public TreeNode buildTree(int[] preorder, int[] inorder) {
24+
Map<Integer, Integer> inorderMap = new HashMap();
25+
for (int i = 0; i < inorder.length; i++) {
26+
inorderMap.put(inorder[i], i);
27+
}
28+
29+
/**At the beginning, both start from 0 to nums.length-1*/
30+
return buildTree(preorder, 0, preorder.length - 1, inorderMap, 0, inorder.length - 1);
2631
}
2732

28-
/**At the beginning, both start from 0 to nums.length-1*/
29-
return buildTree(preorder, 0, preorder.length - 1, inorderMap, 0, inorder.length - 1);
30-
}
31-
32-
private TreeNode buildTree(int[] preorder, int preStart, int preEnd, Map<Integer, Integer> inorderMap, int inStart, int inEnd) {
33-
if (preStart > preEnd || inStart > inEnd) {
34-
return null;
33+
private TreeNode buildTree(int[] preorder, int preStart, int preEnd,
34+
Map<Integer, Integer> inorderMap, int inStart, int inEnd) {
35+
if (preStart > preEnd || inStart > inEnd) {
36+
return null;
37+
}
38+
39+
TreeNode root = new TreeNode(preorder[preStart]);
40+
int inRoot = inorderMap.get(preorder[preStart]);
41+
int numsLeft = inRoot - inStart;
42+
43+
/**It's easy to understand and remember:
44+
* for the indices of inorder array:
45+
* root.left should be inStart and inRoot-1 as new start and end indices
46+
* root.right should be inRoot+1 and inEnd as new start and end indices
47+
*
48+
* since inRoot is being used already in this recursion call, that's why we use inRoot-1 and inRoot+1
49+
* this part is the same for both Leetcode 105 and Leetcode 106.*/
50+
root.left = buildTree(preorder, preStart + 1, preStart + numsLeft, inorderMap, inStart, inRoot - 1);
51+
root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd, inorderMap, inRoot + 1, inEnd);
52+
return root;
3553
}
36-
37-
TreeNode root = new TreeNode(preorder[preStart]);
38-
int inRoot = inorderMap.get(preorder[preStart]);
39-
int numsLeft = inRoot - inStart;
40-
41-
/**It's easy to understand and remember:
42-
* for the indices of inorder array:
43-
* root.left should be inStart and inRoot-1 as new start and end indices
44-
* root.right should be inRoot+1 and inEnd as new start and end indices
45-
*
46-
* since inRoot is being used already in this recursion call, that's why we use inRoot-1 and inRoot+1
47-
* this part is the same for both Leetcode 105 and Leetcode 106.*/
48-
root.left = buildTree(preorder, preStart + 1, preStart + numsLeft, inorderMap, inStart, inRoot - 1);
49-
root.right = buildTree(preorder, preStart + numsLeft + 1, preEnd, inorderMap, inRoot + 1, inEnd);
50-
return root;
5154
}
52-
5355
}

‎src/test/java/com/fishercoder/_105Test.java

Lines changed: 27 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -1,48 +1,41 @@
11
package com.fishercoder;
22

33
import com.fishercoder.common.classes.TreeNode;
4+
import com.fishercoder.common.utils.TreeUtils;
45
import com.fishercoder.solutions._105;
6+
import java.util.Arrays;
57
import org.junit.BeforeClass;
68
import org.junit.Test;
79

810
import static junit.framework.Assert.assertEquals;
911

10-
/**
11-
* Created by fishercoder on 5/1/17.
12-
*/
1312
public class _105Test {
14-
private static _105 test;
15-
private static TreeNode expected;
16-
private static TreeNode actual;
17-
private static int[] preorder;
18-
private static int[] inorder;
13+
private static _105.Solution1 solution1;
14+
private static TreeNode expected;
15+
private static TreeNode actual;
16+
private static int[] preorder;
17+
private static int[] inorder;
1918

20-
@BeforeClass
21-
public static void setup() {
22-
test = new _105();
23-
}
19+
@BeforeClass
20+
public static void setup() {
21+
solution1 = new _105.Solution1();
22+
}
2423

25-
@Test
26-
public void test1() {
27-
preorder = new int[]{1, 2, 3};
28-
inorder = new int[]{2, 1, 3};
29-
actual = test.buildTree(preorder, inorder);
30-
expected = new TreeNode(1);
31-
expected.left = new TreeNode(2);
32-
expected.right = new TreeNode(3);
33-
assertEquals(expected, actual);
34-
}
24+
@Test
25+
public void test1() {
26+
preorder = new int[] {1, 2, 3};
27+
inorder = new int[] {2, 1, 3};
28+
actual = solution1.buildTree(preorder, inorder);
29+
expected = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3));
30+
assertEquals(expected, actual);
31+
}
3532

36-
@Test
37-
public void test2() {
38-
preorder = new int[]{1, 2, 4, 5, 3};
39-
inorder = new int[]{4, 2, 5, 1, 3};
40-
actual = test.buildTree(preorder, inorder);
41-
expected = new TreeNode(1);
42-
expected.left = new TreeNode(2);
43-
expected.right = new TreeNode(3);
44-
expected.left.left = new TreeNode(4);
45-
expected.left.right = new TreeNode(5);
46-
assertEquals(expected, actual);
47-
}
33+
@Test
34+
public void test2() {
35+
preorder = new int[] {1, 2, 4, 5, 3};
36+
inorder = new int[] {4, 2, 5, 1, 3};
37+
actual = solution1.buildTree(preorder, inorder);
38+
expected = TreeUtils.constructBinaryTree(Arrays.asList(1, 2, 3, 4, 5));
39+
assertEquals(expected, actual);
40+
}
4841
}

0 commit comments

Comments
 (0)