Skip to content

Commit dc7f7da

Browse files
fishercoder1534fishercoder1534
committed
improve 105
1 parent 28ba762 commit dc7f7da

File tree

5 files changed

+106
-34
lines changed

5 files changed

+106
-34
lines changed

‎README.md

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -322,7 +322,7 @@ Your ideas/fixes/algorithms are more than welcome!
322322
|109|[Convert Sorted List to Binary Search Tree](https://leetcode.com/problems/convert-sorted-list-to-binary-search-tree/)|[Solution](../master/src/main/java/com/stevesun/solutions/ConvertSortedListtoBinarySearchTree.java)| O(n)|O(h) | Medium | DFS, Recursion
323323
|108|[Convert Sorted Array to Binary Search Tree](https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/)|[Solution](../master/src/main/java/com/stevesun/solutions/ConvertSortedArraytoBinarySearchTree.java)| O(n)|O(h) | Medium| Tree
324324
|107|[Binary Tree Level Order Traversal II](https://leetcode.com/problems/binary-tree-level-order-traversal-ii/)|[Solution](../master/src/main/java/com/stevesun/solutions/BinaryTreeLevelOrderTraversalII.java)| O(nlogn)|O(h) | Easy| BFS
325-
|105|[Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)|[Solution](../master/src/main/java/com/stevesun/solutions/ConstructBinaryTreefromPreorderandInorderTraversal.java)| O(?)|O(?) | Medium|
325+
|105|[Construct Binary Tree from Preorder and Inorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/)|[Solution](../master/src/main/java/com/stevesun/solutions/_105.java)| O(n)|O(n) | Medium| Recursion, Tree
326326
|104|[Maximum Depth of Binary Tree](https://leetcode.com/problems/maximum-depth-of-binary-tree/)|[Solution](../master/src/main/java/com/stevesun/solutions/MaximumDepthOfBinaryTree.java)| O(n)|O(h) | Easy| DFS
327327
|103|[Binary Tree Zigzag Level Order Traversal](https://leetcode.com/problems/binary-tree-zigzag-level-order-traversal/)|[Solution](../master/src/main/java/com/stevesun/solutions/BinaryTreeZigzagLevelOrderTraversal.java)| O(n)|O(h) | Medium| BFS,DFS
328328
|102|[Binary Tree Level Order Traversal](https://leetcode.com/problems/binary-tree-level-order-traversal/)|[Solution](../master/src/main/java/com/stevesun/solutions/BinaryTreeLevelOrderTraversal.java)| O(n)|O(h) | Easy| BFS

‎src/main/java/com/stevesun/common/classes/TreeNode.java

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,26 @@ public class TreeNode {
55
public TreeNode left;
66
public TreeNode right;
77

8+
@Override
9+
public boolean equals(Object o) {
10+
if (this == o) return true;
11+
if (!(o instanceof TreeNode)) return false;
12+
13+
TreeNode treeNode = (TreeNode) o;
14+
15+
if (val != treeNode.val) return false;
16+
if (left != null ? !left.equals(treeNode.left) : treeNode.left != null) return false;
17+
return right != null ? right.equals(treeNode.right) : treeNode.right == null;
18+
}
19+
20+
@Override
21+
public int hashCode() {
22+
int result = val;
23+
result = 31 * result + (left != null ? left.hashCode() : 0);
24+
result = 31 * result + (right != null ? right.hashCode() : 0);
25+
return result;
26+
}
27+
828
@Override
929
public String toString() {
1030
return "TreeNode{" +

‎src/main/java/com/stevesun/solutions/ConstructBinaryTreefromPreorderandInorderTraversal.java

Lines changed: 0 additions & 33 deletions
This file was deleted.

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

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package com.stevesun.solutions;
2+
3+
import com.stevesun.common.classes.TreeNode;
4+
5+
import java.util.HashMap;
6+
import java.util.Map;
7+
8+
/**Given preorder and inorder traversal of a tree, construct the binary tree.
9+
10+
Note:
11+
You may assume that duplicates do not exist in the tree.*/
12+
public class _105 {
13+
14+
//credit: https://discuss.leetcode.com/topic/29838/5ms-java-clean-solution-with-caching
15+
//use HashMap as the cache so that accessing inorder index becomes O(1) time
16+
public TreeNode buildTree(int[] preorder, int[] inorder) {
17+
Map<Integer, Integer> inMap = new HashMap();
18+
for (int i = 0; i < inorder.length; i++) {
19+
inMap.put(inorder[i], i);
20+
}
21+
22+
return buildTree(preorder, 0, preorder.length-1, 0, inorder.length-1, inMap);
23+
}
24+
25+
private TreeNode buildTree(int[] preorder, int preStart, int preEnd, int inStart, int inEnd, Map<Integer, Integer> inMap) {
26+
if (preStart > preEnd || inStart > inEnd) return null;
27+
28+
TreeNode root = new TreeNode(preorder[preStart]);
29+
int inRoot = inMap.get(root.val);
30+
int numsLeft = inRoot - inStart;
31+
32+
root.left = buildTree(preorder, preStart+1, preStart+numsLeft, inStart, inRoot-1, inMap);
33+
root.right = buildTree(preorder, preStart+numsLeft+1, preEnd, inRoot+1, inEnd, inMap);
34+
return root;
35+
}
36+
37+
}

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

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
package com.stevesun;
2+
3+
import com.stevesun.common.classes.TreeNode;
4+
import com.stevesun.solutions._105;
5+
import org.junit.BeforeClass;
6+
import org.junit.Test;
7+
8+
import static junit.framework.Assert.assertEquals;
9+
10+
/**
11+
* Created by stevesun on 5/1/17.
12+
*/
13+
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;
19+
20+
@BeforeClass
21+
public static void setup(){
22+
test = new _105();
23+
}
24+
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+
}
35+
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+
}
48+
}

0 commit comments

Comments
 (0)