Commit38589ac

committed

add a solution for 1008

1 parentb315c79 commit38589acCopy full SHA for 38589ac

File tree

+31

-0

lines changed

src
- main/java/com/fishercoder/solutions
  - _1008.java
- test/java/com/fishercoder
  - _1008Test.java

+31

-0

lines changed

Lines changed: 26 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -23,4 +23,30 @@ private TreeNode bstFromPreorder(int[] preorder, int bound) {`
`23`	`23`	`returnroot;`
`24`	`24`	`}`
`25`	`25`	`}`
	`26`	`+`
	`27`	`+publicstaticclassSolution2 {`
	`28`	`+/**`
	`29`	`+ * I'm happy to have come up with this solution completely on my own on 10/13/2021.Enjoy the beauty of recursion!`
	`30`	`+ */`
	`31`	`+publicTreeNodebstFromPreorder(int[]preorder) {`
	`32`	`+returnbstFromPreorder(preorder,0,preorder.length);`
	`33`	`+ }`
	`34`	`+`
	`35`	`+privateTreeNodebstFromPreorder(int[]preorder,intstart,intend) {`
	`36`	`+if (start >=end) {`
	`37`	`+returnnull;`
	`38`	`+ }`
	`39`	`+TreeNoderoot =newTreeNode(preorder[start]);`
	`40`	`+inti =start +1;`
	`41`	`+for (;i <end;i++) {`
	`42`	`+if (preorder[i] >preorder[start]) {`
	`43`	`+break;`
	`44`	`+ }`
	`45`	`+ }`
	`46`	`+root.left =bstFromPreorder(preorder,start +1,i);`
	`47`	`+root.right =bstFromPreorder(preorder,i,end);`
	`48`	`+returnroot;`
	`49`	`+ }`
	`50`	`+`
	`51`	`+ }`
`26`	`52`	`}`

Lines changed: 5 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -11,19 +11,24 @@`
`11`	`11`
`12`	`12`	`publicclass_1008Test {`
`13`	`13`	`privatestatic_1008.Solution1solution1;`
	`14`	`+privatestatic_1008.Solution2solution2;`
`14`	`15`	`privatestaticint[]preorder;`
`15`	`16`	`privatestaticTreeNodeexpected;`
`16`	`17`	`privatestaticTreeNodeactual;`
`17`	`18`
`18`	`19`	`@Test`
`19`	`20`	`publicvoidtest1() {`
`20`	`21`	`solution1 =new_1008.Solution1();`
	`22`	`+solution2 =new_1008.Solution2();`
`21`	`23`	`preorder =newint[]{8,5,1,7,10,12};`
`22`	`24`	`expected =TreeUtils.constructBinaryTree(Arrays.asList(8,5,10,1,7,null,12));`
`23`	`25`	`TreeUtils.printBinaryTree(expected);`
`24`	`26`	`actual =solution1.bstFromPreorder(preorder);`
`25`	`27`	`TreeUtils.printBinaryTree(actual);`
`26`	`28`	`assertEquals(expected,actual);`
	`29`	`+actual =solution2.bstFromPreorder(preorder);`
	`30`	`+TreeUtils.printBinaryTree(actual);`
	`31`	`+assertEquals(expected,actual);`
`27`	`32`	`}`
`28`	`33`
`29`	`34`	`}`

Comments

(0)