Skip to content

Commit 35a0f61

Browse files
add 106
1 parent c5bf94e commit 35a0f61

File tree

3 files changed

+112
-0
lines changed

3 files changed

+112
-0
lines changed

README.md

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -334,6 +334,7 @@ Your ideas/fixes/algorithms are more than welcome!
334334
|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
335335
|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
336336
|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
337+
|106|[Construct Binary Tree from Inorder and Postorder Traversal](https://leetcode.com/problems/construct-binary-tree-from-inorder-and-postorder-traversal/)|[Solution](../master/src/main/java/com/stevesun/solutions/_106.java)| O(n)|O(n) | Medium| Recursion, Tree
337338
|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
338339
|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
339340
|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
Lines changed: 45 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,45 @@
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+
/**
9+
* 106. Construct Binary Tree from Inorder and Postorder Traversal
10+
*
11+
* Given inorder and postorder traversal of a tree, construct the binary tree.
12+
13+
Note:
14+
You may assume that duplicates do not exist in the tree.
15+
16+
*/
17+
public class _106 {
18+
19+
//credit: https://discuss.leetcode.com/topic/3296/my-recursive-java-code-with-o-n-time-and-o-n-space
20+
/**The idea is to take the last element in postorder as the root; find the position of the root in the inorder array; then locate the range for left sub-tree and right sub-tree and do recursion,
21+
* use a hashmap to record the index of root in the inorder array.*/
22+
public TreeNode buildTree(int[] inorder, int[] postorder) {
23+
if (inorder == null || postorder == null || inorder.length != postorder.length) {
24+
return null;
25+
}
26+
HashMap<Integer, Integer> map = new HashMap<>();
27+
for (int i = 0; i < inorder.length; i++) {
28+
map.put(inorder[i], i);
29+
}
30+
return buildTreeRecursively(0, inorder.length-1, postorder, 0, postorder.length-1,map);
31+
}
32+
33+
private TreeNode buildTreeRecursively(int inorderStart, int inorderEnd, int[] postorder, int postorderStart, int postorderEnd, Map<Integer, Integer> map){
34+
if (postorderStart > postorderEnd || inorderStart > inorderEnd) return null;
35+
TreeNode root = new TreeNode(postorder[postorderEnd]);
36+
int inRoot = map.get(postorder[postorderEnd]);
37+
TreeNode leftchild = buildTreeRecursively(inorderStart, inRoot-1, postorder, postorderStart, postorderStart+inRoot-inorderStart-1, map);
38+
TreeNode rightchild = buildTreeRecursively(inRoot+1, inorderEnd, postorder, postorderStart+inRoot-inorderStart, postorderEnd-1, map);
39+
root.left = leftchild;
40+
root.right = rightchild;
41+
return root;
42+
}
43+
44+
45+
}
Lines changed: 66 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,66 @@
1+
package com.stevesun;
2+
3+
import com.stevesun.common.classes.TreeNode;
4+
import com.stevesun.solutions._106;
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/12/17.
12+
*/
13+
public class _106Test {
14+
private static _106 test;
15+
private static TreeNode expected;
16+
private static TreeNode actual;
17+
private static int[] inorder;
18+
private static int[] postorder;
19+
20+
@BeforeClass
21+
public static void setup(){
22+
test = new _106();
23+
}
24+
25+
@Test
26+
public void test1(){
27+
/**it should be a tree like this:
28+
* 3
29+
* /
30+
* 1
31+
* \
32+
* 2
33+
*/
34+
inorder = new int[]{2,1,3};
35+
postorder = new int[]{1,2,3};
36+
actual = test.buildTree(postorder, inorder);
37+
expected = new TreeNode(3);
38+
expected.left = new TreeNode(1);
39+
expected.left.right = new TreeNode(2);
40+
assertEquals(expected, actual);
41+
}
42+
43+
@Test
44+
public void test2(){
45+
/**it should be a tree like this:
46+
* 3
47+
* /
48+
* 1
49+
* \
50+
* 5
51+
* /
52+
* 2
53+
* \
54+
* 4
55+
*/
56+
inorder = new int[]{4,2,5,1,3};
57+
postorder = new int[]{1,2,4,5,3};
58+
actual = test.buildTree(postorder, inorder);
59+
expected = new TreeNode(3);
60+
expected.left = new TreeNode(1);
61+
expected.left.right = new TreeNode(5);
62+
expected.left.right.left = new TreeNode(2);
63+
expected.left.right.left.right = new TreeNode(4);
64+
assertEquals(expected, actual);
65+
}
66+
}

0 commit comments

Comments
 (0)