Задача: 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 {
    function validateBinaryTreeNodes($n, $leftChild, $rightChild) {
        $parents = array_fill(0, $n, 0);

        for ($i = 0; $i < $n; $i++) {
            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;
                }
            }
        }

        $root = -1;
        for ($i = 0; $i < $n; $i++) {
            if ($parents[$i] == 0) {
                if ($root == -1) {
                    $root = $i;
                } else {
                    return false;
                }
            }
        }

        if ($root == -1) {
            return false;
        }

        $visited = [];
        $queue = [$root];

        while (!empty($queue)) {
            $node = array_shift($queue);
            if (in_array($node, $visited)) {
                return false;
            }
            $visited[] = $node;
            if ($leftChild[$node] != -1) {
                $queue[] = $leftChild[$node];
            }
            if ($rightChild[$node] != -1) {
                $queue[] = $rightChild[$node];
            }
        }

        return count($visited) == $n;
    }
}

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