1361.验证二叉树

https://leetcode-cn.com/problems/validate-binary-tree-nodes/

一：连通性判定

遍历数组 leftChild 和 rightChild，如果数组中的某个元素 x 不为 -1，那么就表示有一条边指向节点 x，节点 x 的入度 indeg[x] 增加 1。遍历完成后找入度为0的结点作为root（可能有多个，后面解决）

从root开始，用bfs遍历，当遇到已经访问过的结点，说明该节点入度大于1，而二叉树除根节点外每个节点入度为1，即判定不是二叉树

遍历结束，当访问过的结点数不等于n，说明存在两个以上的根节点，判断不是二叉树

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild , rightChild) :
        indeg = [0]*n
        #统计入度
        for i in range(n):
            if leftChild[i] != -1:
                indeg[leftChild[i]] +=1
            if rightChild[i] != -1:
                indeg[rightChild[i]] +=1
            # print(indeg)
        root = -1
        #找一个入度为0的作为root
        for i in range(n):
            if indeg[i] == 0:
                root = i
                break
        if root == -1:
            return False
        q = [root]
        visited = set([root])
        while q:
            node = q.pop(0)
            #左子
            left = leftChild[node]
            if left != -1:
                #入队时就标记访问
                if left in visited:
                    return False
                visited.add(left)
                q.append(left)
            #右子
            right = rightChild[node]
            if right != -1:
                if right in visited:
                    return False
                visited.add(right)
                q.append(right)
        return len(visited) == n