1361. Validate Binary Tree Nodes

step 1: find root

root should not be child of any other node
there should be exact one node. No more, no less

step 2: bfs traverse and no node can be re-visited

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        root = set()
        for i in range(n):
            root.add(i)
        
        for i in range(n):
            if leftChild[i] in root and leftChild[i] != -1:
                root.remove(leftChild[i])
            if rightChild[i] in root and rightChild[i] != -1:
                root.remove(rightChild[i])
        
        if len(root) != 1:
            return False
        
        queue = collections.deque(list(root))
        visited = set(list(root))
        while queue:
            node = queue.popleft()
            if leftChild[node] != -1:
                if leftChild[node] in visited:
                    return False
                visited.add(leftChild[node])
                queue.append(leftChild[node])
            if rightChild[node] != -1:
                if rightChild[node] in visited:
                    return False
                visited.add(rightChild[node])
                queue.append(rightChild[node])
        return len(visited) == n

1361. Validate Binary Tree Nodes - cocoder39/coco39_LC GitHub Wiki