Python | LeetCode
Задача: 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
Ставь 👍 и забирай 📚 Базу знаний
2 · 760 ·