1361

main.py

#buggy code took 20 minutes
class Solution:
    def validateBinaryTreeNodes(
        self, n: int, leftChild: List[int], rightChild: List[int]
    ) -> bool:

        nparent = [0] * n
        for i in range(n):

            leftv = nparent[leftChild[i]]
            if leftv != -1:
                nparent[leftv] += 1

            rightv = nparent[rightChild[i]]
            if rightv != -1:
                nparent[rightv] += 1
        
        count = 0
        for v in nparent:
            if v>1:
                return False
            if v == 0:
                count += 1
        
        if count!=1:
            return False
        
        # find cycles
        # return true if find cycle
        def dfs(v,visited):
            
            visited[v]=1
            
            
            for node in (leftChild[v],rightChild[v]):
                if node!=-1:
                    if visited[node]==0:
                        if dfs(node,visited):
                            return True
                    if visited[node]==1:
                        return True
            
            visited[v]=2
            return False
        visited=[0]*n
        for i in range(n):
            if visited[i]==0:
                if dfs(i,visited):
                    return False
        return True