1361. Validate Binary Tree Nodes - Explanation

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        hasParent = set(leftChild + rightChild)
        hasParent.discard(-1)
        if len(hasParent) == n:
            return False

        root = -1
        for i in range(n):
            if i not in hasParent:
                root = i
                break

        visit = set()
        def dfs(i):
            if i == -1:
                return True
            if i in visit:
                return False
            visit.add(i)
            return dfs(leftChild[i]) and dfs(rightChild[i])

        return dfs(root) and len(visit) == n

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: list[int], rightChild: list[int]) -> bool:
        indegree = [0] * n
        for i in range(n):
            if leftChild[i] != -1:
                indegree[leftChild[i]] += 1
                if indegree[leftChild[i]] > 1:
                    return False
            if rightChild[i] != -1:
                indegree[rightChild[i]] += 1
                if indegree[rightChild[i]] > 1:
                    return False

        root = -1
        for i in range(n):
            if indegree[i] == 0:
                if root != -1:
                    return False
                root = i

        if root == -1:
            return False

        count = 0
        q = deque([root])
        while q:
            i = q.popleft()
            count += 1
            if leftChild[i] != -1:
                q.append(leftChild[i])
            if rightChild[i] != -1:
                q.append(rightChild[i])
        return count == n

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: list[int], rightChild: list[int]) -> bool:
        indegree = [0] * n
        for i in range(n):
            if leftChild[i] != -1:
                indegree[leftChild[i]] += 1
                if indegree[leftChild[i]] > 1:
                    return False
            if rightChild[i] != -1:
                indegree[rightChild[i]] += 1
                if indegree[rightChild[i]] > 1:
                    return False

        root = next((i for i in range(n) if indegree[i] == 0), -1)
        if root == -1:
            return False

        count, stack = 0, [root]
        while stack:
            node = stack.pop()
            count += 1
            if leftChild[node] != -1:
                stack.append(leftChild[node])
            if rightChild[node] != -1:
                stack.append(rightChild[node])

        return count == n

class DSU:
    def __init__(self, n):
        self.Parent = list(range(n))
        self.Components = n

    def find(self, node):
        if self.Parent[node] != node:
            self.Parent[node] = self.find(self.Parent[node])
        return self.Parent[node]

    def union(self, parent, child):
        parentRoot = self.find(parent)
        childRoot = self.find(child)
        if childRoot != child or parentRoot == childRoot:
            return False

        self.Components -= 1
        self.Parent[childRoot] = parentRoot
        return True

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: list[int], rightChild: list[int]) -> bool:
        dsu = DSU(n)

        for parent in range(n):
            for child in (leftChild[parent], rightChild[parent]):
                if child == -1:
                    continue
                if not dsu.union(parent, child):
                    return False

        return dsu.Components == 1