Commit5d3baf8

authored

Create 1361-validate-binary-tree-nodes.java

1 parent2746c43 commit5d3baf8Copy full SHA for 5d3baf8

File tree

+47

-0

lines changed

+47

-0

lines changed

Lines changed: 47 additions & 0 deletions

Original file line number	Diff line number	Diff line change
`@@ -0,0 +1,47 @@`
	`1`	`+/* BFS`
	`2`	`+--------------------------------`
	`3`	`+ Time Complexity: O(n)`
	`4`	`+ Space Complexity: O(n)`
	`5`	`+------------------------------*/`
	`6`	`+`
	`7`	`+classSolution {`
	`8`	`+publicbooleanvalidateBinaryTreeNodes(intn,int[]leftChild,int[]rightChild) {`
	`9`	`+introot =findRoot(n,leftChild,rightChild);`
	`10`	`+if(root == -1)`
	`11`	`+returnfalse;`
	`12`	`+`
	`13`	`+Set<Integer>visited =newHashSet<>();`
	`14`	`+Queue<Integer>q =newLinkedList<>();`
	`15`	`+`
	`16`	`+q.add(root);`
	`17`	`+visited.add(root);`
	`18`	`+`
	`19`	`+while(!q.isEmpty()){`
	`20`	`+intnode =q.poll();`
	`21`	`+int[]childerns = {leftChild[node],rightChild[node]};`
	`22`	`+`
	`23`	`+for(intc:childerns){`
	`24`	`+if(c == -1)`
	`25`	`+continue;`
	`26`	`+if(visited.contains(c))`
	`27`	`+returnfalse;`
	`28`	`+q.add(c);`
	`29`	`+visited.add(c);`
	`30`	`+ }`
	`31`	`+ }`
	`32`	`+returnvisited.size() ==n;`
	`33`	`+ }`
	`34`	`+privateintfindRoot(intn,int[]leftChild,int[]rightChild){`
	`35`	`+Set<Integer>set =newHashSet<>();`
	`36`	`+for(intlc:leftChild)`
	`37`	`+set.add(lc);`
	`38`	`+for(intrc:rightChild)`
	`39`	`+set.add(rc);`
	`40`	`+`
	`41`	`+for(inti =0;i <n;i++){`
	`42`	`+if(!set.contains(i))`
	`43`	`+returni;`
	`44`	`+ }`
	`45`	`+return -1;`
	`46`	`+ }`
	`47`	`+}`

Comments

(0)