Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commita214676

Browse files
add a solution for 106
1 parent8014ff0 commita214676

File tree

2 files changed

+32
-1
lines changed

2 files changed

+32
-1
lines changed

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

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -56,4 +56,31 @@ private TreeNode buildTreeRecursively(Map<Integer, Integer> inorderMap, int inor
5656
returnroot;
5757
}
5858
}
59+
60+
publicstaticclassSolution2 {
61+
/**
62+
* My own solution after inspiration from LeetCode 105.
63+
* 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.
64+
* 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.
65+
*/
66+
publicTreeNodebuildTree(int[]inorder,int[]postorder) {
67+
Map<Integer,Integer>inMap =newHashMap<>();
68+
for (inti =0;i <inorder.length;i++) {
69+
inMap.put(inorder[i],i);
70+
}
71+
returnhelper(postorder,inorder,inMap,postorder.length -1,0,0,inorder.length -1);
72+
}
73+
74+
privateTreeNodehelper(int[]postorder,int[]inorder,Map<Integer,Integer>inMap,intpostStart,intpostEnd,intinStart,intinEnd) {
75+
if (postStart <postEnd) {
76+
returnnull;
77+
}
78+
intinRoot =inMap.get(postorder[postStart]);
79+
intnumsRight =inEnd -inRoot;
80+
TreeNodenode =newTreeNode(postorder[postStart]);
81+
node.right =helper(postorder,inorder,inMap,postStart -1,postStart -numsRight,inRoot +1,inEnd);
82+
node.left =helper(postorder,inorder,inMap,postStart -numsRight -1,postEnd,inStart,inRoot -1);
83+
returnnode;
84+
}
85+
}
5986
}

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

Lines changed: 5 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -12,6 +12,7 @@
1212

1313
publicclass_106Test {
1414
privatestatic_106.Solution1solution1;
15+
privatestatic_106.Solution2solution2;
1516
privatestaticTreeNodeexpected;
1617
privatestaticTreeNodeactual;
1718
privatestaticint[]inorder;
@@ -20,6 +21,7 @@ public class _106Test {
2021
@BeforeClass
2122
publicstaticvoidsetup() {
2223
solution1 =new_106.Solution1();
24+
solution2 =new_106.Solution2();
2325
}
2426

2527
@Test
@@ -36,6 +38,8 @@ public void test1() {
3638
actual =solution1.buildTree(inorder,postorder);
3739
expected =TreeUtils.constructBinaryTree(Arrays.asList(3,1,null,null,2));
3840
assertEquals(expected,actual);
41+
actual =solution2.buildTree(inorder,postorder);
42+
assertEquals(expected,actual);
3943
}
4044

4145
@Test
@@ -52,7 +56,7 @@ public void test2() {
5256
* 4
5357
*/
5458
postorder =newint[]{4,2,5,1,3};
55-
inorder=newint[]{1,2,4,5,3};
59+
inorder =newint[]{1,2,4,5,3};
5660
actual =solution1.buildTree(inorder,postorder);
5761
expected =TreeUtils.constructBinaryTree(Arrays.asList(3,1,null,null,5,2,null,null,4));
5862
assertEquals(expected,actual);

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp