Задача: 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 {
    fun validateBinaryTreeNodes(n: Int, leftChild: IntArray, rightChild: IntArray): Boolean {
        val parents = IntArray(n)
        
        for (i in 0 until n) {
            if (leftChild[i] != -1) {
                parents[leftChild[i]]++
                if (parents[leftChild[i]] > 1) {
                    return false
                }
            }
            if (rightChild[i] != -1) {
                parents[rightChild[i]]++
                if (parents[rightChild[i]] > 1) {
                    return false
                }
            }
        }
        
        var root = -1
        for (i in 0 until n) {
            if (parents[i] == 0) {
                if (root == -1) {
                    root = i
                } else {
                    return false
                }
            }
        }
        
        if (root == -1) {
            return false
        }
        
        val visited = mutableSetOf<Int>()
        val queue = ArrayDeque<Int>()
        queue.add(root)
        
        while (queue.isNotEmpty()) {
            val node = queue.removeFirst()
            if (visited.contains(node)) {
                return false
            }
            visited.add(node)
            if (leftChild[node] != -1) {
                queue.add(leftChild[node])
            }
            if (rightChild[node] != -1) {
                queue.add(rightChild[node])
            }
        }
        
        return visited.size == n
    }
}

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