Commitadb3b2d

authored

added solution and test cases for 1145 (fishercoder1534#153)

1 parentdb7b16b commitadb3b2dCopy full SHA for adb3b2d

File tree

+63

-0

lines changed

src
- main/java/com/fishercoder/solutions
  - _1145.java
- test/java/com/fishercoder
  - _1145Test.java

+63

-0

lines changed

Lines changed: 30 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,30 @@`
	`1`	`+packagecom.fishercoder.solutions;`
	`2`	`+`
	`3`	`+importcom.fishercoder.common.classes.TreeNode;`
	`4`	`+publicclass_1145 {`
	`5`	`+publicstaticclassSolution1 {`
	`6`	`+publicbooleanbtreeGameWinningMove(TreeNoderoot,intn,intx) {`
	`7`	`+if (root ==null) {`
	`8`	`+returnfalse;`
	`9`	`+ }`
	`10`	`+`
	`11`	`+if (root.val ==x) {`
	`12`	`+// 3 possible paths to block, left, right, parent`
	`13`	`+intleftCount =countNodes(root.left);`
	`14`	`+intrightCount =countNodes(root.right);`
	`15`	`+intparent =n - (leftCount +rightCount +1);`
	`16`	`+`
	`17`	`+// possible to win if no. of nodes in 1 path is > than sum of nodes in the other 2 paths`
	`18`	`+returnparent > (leftCount +rightCount) \|\|leftCount > (parent +rightCount) \|\|rightCount > (parent +leftCount);`
	`19`	`+ }`
	`20`	`+returnbtreeGameWinningMove(root.left,n,x) \|\|btreeGameWinningMove(root.right,n,x);`
	`21`	`+ }`
	`22`	`+`
	`23`	`+privateintcountNodes(TreeNoderoot) {`
	`24`	`+if (root ==null) {`
	`25`	`+return0;`
	`26`	`+ }`
	`27`	`+returncountNodes(root.left) +countNodes(root.right) +1;`
	`28`	`+ }`
	`29`	`+ }`
	`30`	`+}`

Lines changed: 33 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,33 @@`
	`1`	`+packagecom.fishercoder;`
	`2`	`+`
	`3`	`+importcom.fishercoder.common.classes.TreeNode;`
	`4`	`+importcom.fishercoder.common.utils.TreeUtils;`
	`5`	`+importcom.fishercoder.solutions._1145;`
	`6`	`+importorg.junit.Assert;`
	`7`	`+importorg.junit.BeforeClass;`
	`8`	`+importorg.junit.Test;`
	`9`	`+`
	`10`	`+importjava.util.Arrays;`
	`11`	`+`
	`12`	`+importstaticjunit.framework.Assert.assertEquals;`
	`13`	`+`
	`14`	`+publicclass_1145Test {`
	`15`	`+`
	`16`	`+privatestatic_1145.Solution1solution1;`
	`17`	`+privatestaticTreeNoderoot1;`
	`18`	`+privatestaticintn;`
	`19`	`+privatestaticintx;`
	`20`	`+`
	`21`	`+@BeforeClass`
	`22`	`+publicstaticvoidsetup() {`
	`23`	`+solution1 =new_1145.Solution1();`
	`24`	`+ }`
	`25`	`+`
	`26`	`+@Test`
	`27`	`+publicvoidtest1() {`
	`28`	`+root1 =TreeUtils.constructBinaryTree(Arrays.asList(1,2,3,4,5,6,7,8,9,10,11));`
	`29`	`+n =11;`
	`30`	`+x =3;`
	`31`	`+Assert.assertEquals(true,solution1.btreeGameWinningMove(root1,n,x));`
	`32`	`+ }`
	`33`	`+}`

Comments

(0)