<p>You have <code>n</code> binary tree nodes numbered from <code>0</code> to <code>n - 1</code> where node <code>i</code> has two children <code>leftChild[i]</code> and <code>rightChild[i]</code>, return <code>true</code> if and only if <strong>all</strong> the given nodes form <strong>exactly one</strong> valid binary tree.</p>

<p>If node <code>i</code> has no left child then <code>leftChild[i]</code> will equal <code>-1</code>, similarly for the right child.</p>

<p>Note that the nodes have no values and that we only use the node numbers in this problem.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/08/23/1503_ex1.png" style="width: 195px; height: 287px;" />
<pre>
<strong>Input:</strong> n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
<strong>Output:</strong> true
</pre>

<p><strong class="example">Example 2:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/08/23/1503_ex2.png" style="width: 183px; height: 272px;" />
<pre>
<strong>Input:</strong> n = 4, leftChild = [1,-1,3,-1], rightChild = [2,3,-1,-1]
<strong>Output:</strong> false
</pre>

<p><strong class="example">Example 3:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2019/08/23/1503_ex3.png" style="width: 82px; height: 174px;" />
<pre>
<strong>Input:</strong> n = 2, leftChild = [1,0], rightChild = [-1,-1]
<strong>Output:</strong> false
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>n == leftChild.length == rightChild.length</code></li>
	<li><code>1 &lt;= n &lt;= 10<sup>4</sup></code></li>
	<li><code>-1 &lt;= leftChild[i], rightChild[i] &lt;= n - 1</code></li>
</ul>

class Node:
    def __init__(self, val:int=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

class Solution:
    def _gen_graph(self, left_child, right_child):
        graph = collections.defaultdict(lambda: Node())
        indegrees = collections.defaultdict(int)

        for i in range(len(left_child)):
            node = graph[i]
            
            if left_child[i] != -1:
                node.left = graph[left_child[i]]
                indegrees[left_child[i]] += 1
            
            if right_child[i] != -1:
                node.right = graph[right_child[i]]
                indegrees[right_child[i]] += 1
        
        root_nodes = [i for i in range(len(left_child)) if indegrees[i] == 0]
        return graph, root_nodes

    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        graph, root_nodes = self._gen_graph(leftChild, rightChild)    

        if len(root_nodes) != 1:
            return False
        
        visited = {graph[root_nodes[0]]}

        def dfs(node):
            if node.left and node.left in visited:
                return False
            
            if node.right and node.right in visited:
                return False
            
            if node.left:
                visited.add(node.left)
                if not dfs(node.left): return False
            
            if node.right:
                visited.add(node.right)
                if not dfs(node.right): return False

            return True
        
        if not dfs(graph[root_nodes[0]]):
            return False
        
        for i in range(len(leftChild)):
            if graph[i] not in visited:
                return False
        
        return True
26710