Задача: 1361. Validate Binary Tree Nodes
Сложность: easy

У вас есть n узлов бинарного дерева, пронумерованных от 0 до n-1, где узел i имеет двух детей: leftChild[i] и rightChild[i]. Верните true, если и только если все заданные узлы образуют ровно одно допустимое бинарное дерево.

Если у узла i нет левого ребенка, то leftChild[i] будет равен -1, аналогично для правого ребенка.

Обратите внимание, что узлы не имеют значений и мы используем только номера узлов в этой задаче.

Пример:

Input: n = 4, leftChild = [1,-1,3,-1], rightChild = [2,-1,-1,-1]
Output: true

👨‍💻 Алгоритм:

1⃣Проверка количества родителей для каждого узла:
Создайте массив для отслеживания количества родителей для каждого узла. Проходите через leftChild и rightChild, увеличивая счетчик для каждого ребенка. Если какой-либо узел имеет более одного родителя, возвращайте false.

2⃣Поиск корневого узла и проверка на единственное дерево:
Найдите корневой узел (узел с нулевым количеством родителей). Если корневых узлов нет или больше одного, верните false. Используйте BFS или DFS, чтобы проверить, что все узлы достижимы от корня и что нет циклов.

3⃣Проверка на достижение всех узлов:
Проверьте, что количество посещенных узлов равно n. Если нет, верните false. В противном случае, верните true.
😎 Решение:

class Solution:
    def validateBinaryTreeNodes(self, n: int, leftChild: List[int], rightChild: List[int]) -> bool:
        parents = [0] * n
        
        for i in range(n):
            if leftChild[i] != -1:
                parents[leftChild[i]] += 1
                if parents[leftChild[i]] > 1:
                    return False
            if rightChild[i] != -1:
                parents[rightChild[i]] += 1
                if parents[rightChild[i]] > 1:
                    return False
        
        root = -1
        for i in range(n):
            if parents[i] == 0:
                if root == -1:
                    root = i
                else:
                    return False
        
        if root == -1:
            return False
        
        visited = set()
        queue = [root]
        
        while queue:
            node = queue.pop(0)
            if node in visited:
                return False
            visited.add(node)
            if leftChild[node] != -1:
                queue.append(leftChild[node])
            if rightChild[node] != -1:
                queue.append(rightChild[node])
        
        return len(visited) == n

Ставь 👍 и забирай 📚 Базу знаний

Пожизненный PRO доступ на easyoffer — по цене одного года!

До 2 сентября вы можете купить PRO навсегда.
Покупаешь один раз — пользуешься всю жизнь.

– База вопросов и задач из собеседований
– Примеры видео-ответов на вопросы
– Записи реальных собеседований
– Тренажеры "Проработка вопросов" и "Реальное собеседование"
– Аналитика требований из вакансий
– Автоотклики на вакансии
– Агрегатор вакансий (скоро)

👉 Купить PRO со скидкой 70%: https://easyoffer.ru/pro