1275-validate-binary-tree-nodes.kt

importjava.util.*

classSolution {
funvalidateBinaryTreeNodes(n:Int, leftChild:IntArray, rightChild:IntArray): Boolean {
val parents =IntArray(n) { -1 }

funbfsCheckCycle(start:Int): Boolean {
val queue:Queue<Int> =LinkedList()
 queue.add(start)
 parents[start] = start

while (queue.isNotEmpty()) {
val node = queue.poll()

listOf(
 leftChild[node],
 rightChild[node]
 ).forEach { next ->
if (next ==-1)
return@forEach

if (parents[next] == start)
returnfalse
if (parents[next] == next) {
 parents[next] = start
return@forEach
 }

 parents[next] = start
 queue.add(next)
 }
 }

returntrue
 }

for (node in0 until n) {
if (parents[node] ==-1)
if (!bfsCheckCycle(node))
returnfalse
 }

var count =0
for (i in0 until n) {
if (parents[i] == i)
++count

if (count >1)
returnfalse
 }
return count ==1
 }
}