1361. Validate Binary Tree Nodes

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        """ tc O(N) sc O(N) 
        对于一个包含 n 个节点 m 条边的无向图，如果它是一棵树，那么必须满足以下三个条件中的两个：
            m = n - 1；

            该无向图连通；

            该无向图无环。
        main idea:  topological sort + DFS  
        to validate it's  a valid tree:  1. edges = n - 1  => only one parent => indegree for each node (except for root) is 1 (2) no cycles/ all can be visited   ==> DFS traverse 
        """
        indegree = [0] * n 
        # level order traversal 
        for l, r in zip(leftChild, rightChild):
            if l != -1:
                indegree[l] += 1
                if indegree[l] > 1: return False 
            if r != -1:
                indegree[r] += 1 
                if indegree[r] > 1: return False 
            
        # find root, check there is only one root and topological sort to remove indegree 
        q = [root for root in range(len(indegree)) if indegree[root]==0]
        if len(q) != 1: return False 
        
        # topogolical sort, check all nodes can be visited 
        for node in q : 
            for child in leftChild[node],rightChild[node]:
                seen.add(child)
                if child == -1: continue 
                indegree[child] -= 1 
                if indegree[child] == 0:
                    q.append(child)
        return sum(indegree) == 0