Commit9dfc62c

committed

add 669

1 parent2f1856a commit9dfc62cCopy full SHA for 9dfc62c

File tree

+107

-0

lines changed

README.md
src
- main/java/com/fishercoder/solutions
  - _669.java
- test/java/com/fishercoder
  - _669Test.java

+107

-0

lines changed

Lines changed: 1 addition & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -23,6 +23,7 @@ Your ideas/fixes/algorithms are more than welcome!`
`23`	`23`	`\| # \| Title \| Solutions \| Time \| Space \| Difficulty \| Tag \| Notes`
`24`	`24`	`\|-----\|----------------\|---------------\|---------------\|---------------\|-------------\|--------------\|-----`
`25`	`25`	`\|671\|[Second Minimum Node In a Binary Tree](https://leetcode.com/problems/second-minimum-node-in-a-binary-tree/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_671.java) \| O(n) \| O(n) \| Easy \| Tree, DFS`
	`26`	`+\|669\|[Trim a Binary Search Tree](https://leetcode.com/problems/trim-a-binary-search-tree/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_669.java) \| O(n) \| O(1) \| Easy \| Tree, DFS`
`26`	`27`	`\|668\|[Kth Smallest Number in Multiplication Table](https://leetcode.com/problems/kth-smallest-number-in-multiplication-table/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_668.java) \| O(logm*n) \| O(1) \| Hard \| Binary Search`
`27`	`28`	`\|667\|[Beautiful Arrangement II](https://leetcode.com/problems/beautiful-arrangement-ii/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_667.java) \| O(n) \| O(1) \| Medium \| Array`
`28`	`29`	`\|666\|[Path Sum IV](https://leetcode.com/problems/path-sum-iv/)\|[Solution](../master/src/main/java/com/fishercoder/solutions/_666.java) \| O(1) \| O(1) \| Medium \| Tree, DFS`

Lines changed: 69 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,69 @@`
	`1`	`+packagecom.fishercoder.solutions;`
	`2`	`+`
	`3`	`+importcom.fishercoder.common.classes.TreeNode;`
	`4`	`+`
	`5`	`+/**`
	`6`	`+ * 669. Trim a Binary Search Tree`
	`7`	`+ *`
	`8`	`+ * Given a binary search tree and the lowest and highest boundaries as L and R,`
	`9`	`+ * trim the tree so that all its elements lies in [L, R] (R >= L).`
	`10`	`+ * You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.`
	`11`	`+`
	`12`	`+ Example 1:`
	`13`	`+`
	`14`	`+ Input:`
	`15`	`+ 1`
	`16`	`+ / \`
	`17`	`+ 0 2`
	`18`	`+`
	`19`	`+ L = 1`
	`20`	`+ R = 2`
	`21`	`+`
	`22`	`+ Output:`
	`23`	`+ 1`
	`24`	`+ \`
	`25`	`+ 2`
	`26`	`+`
	`27`	`+ Example 2:`
	`28`	`+`
	`29`	`+ Input:`
	`30`	`+ 3`
	`31`	`+ / \`
	`32`	`+0 4`
	`33`	`+ \`
	`34`	`+ 2`
	`35`	`+ /`
	`36`	`+1`
	`37`	`+`
	`38`	`+ L = 1`
	`39`	`+ R = 3`
	`40`	`+`
	`41`	`+ Output:`
	`42`	`+ 3`
	`43`	`+ /`
	`44`	`+ 2`
	`45`	`+ /`
	`46`	`+1`
	`47`	`+`
	`48`	`+ */`
	`49`	`+publicclass_669 {`
	`50`	`+publicstaticclassSolution1 {`
	`51`	`+publicTreeNodetrimBST(TreeNoderoot,intL,intR) {`
	`52`	`+if (root ==null) {`
	`53`	`+returnroot;`
	`54`	`+ }`
	`55`	`+`
	`56`	`+if (root.val >R) {`
	`57`	`+returntrimBST(root.left,L,R);`
	`58`	`+ }`
	`59`	`+`
	`60`	`+if (root.val <L) {`
	`61`	`+returntrimBST(root.right,L,R);`
	`62`	`+ }`
	`63`	`+`
	`64`	`+root.left =trimBST(root.left,L,R);`
	`65`	`+root.right =trimBST(root.right,L,R);`
	`66`	`+returnroot;`
	`67`	`+ }`
	`68`	`+ }`
	`69`	`+}`

Lines changed: 37 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,37 @@`
	`1`	`+packagecom.fishercoder;`
	`2`	`+`
	`3`	`+importcom.fishercoder.common.classes.TreeNode;`
	`4`	`+importcom.fishercoder.common.utils.TreeUtils;`
	`5`	`+importcom.fishercoder.solutions._669;`
	`6`	`+importorg.junit.BeforeClass;`
	`7`	`+importorg.junit.Test;`
	`8`	`+`
	`9`	`+importjava.util.Arrays;`
	`10`	`+`
	`11`	`+importstaticorg.junit.Assert.assertEquals;`
	`12`	`+`
	`13`	`+publicclass_669Test {`
	`14`	`+privatestatic_669.Solution1solution1;`
	`15`	`+privatestaticTreeNoderoot;`
	`16`	`+privatestaticTreeNodeexpected;`
	`17`	`+`
	`18`	`+@BeforeClass`
	`19`	`+publicstaticvoidsetup() {`
	`20`	`+solution1 =new_669.Solution1();`
	`21`	`+ }`
	`22`	`+`
	`23`	`+@Test`
	`24`	`+publicvoidtest1() {`
	`25`	`+root =TreeUtils.constructBinaryTree(Arrays.asList(1,0,2));`
	`26`	`+expected =TreeUtils.constructBinaryTree(Arrays.asList(1,null,2));`
	`27`	`+assertEquals(expected,solution1.trimBST(root,1,2));`
	`28`	`+ }`
	`29`	`+`
	`30`	`+@Test`
	`31`	`+publicvoidtest2() {`
	`32`	`+root =TreeUtils.constructBinaryTree(Arrays.asList(3,0,4,null,2,null,null,1));`
	`33`	`+expected =TreeUtils.constructBinaryTree(Arrays.asList(3,2,null,1));`
	`34`	`+assertEquals(expected,solution1.trimBST(root,1,3));`
	`35`	`+ }`
	`36`	`+`
	`37`	`+}`

Comments

(0)