Сложность: medium
Вам дан корень бинарного дерева и целое число distance. Пара двух различных листовых узлов бинарного дерева называется хорошей, если длина кратчайшего пути между ними меньше или равна distance.
Верните количество хороших пар листовых узлов в дереве.
Пример:
Input: root = [1,2,3,null,4], distance = 3
Output: 1
Explanation: The leaf nodes of the tree are 3 and 4 and the length of the shortest path between them is 3. This is the only good pair.
👨💻 Алгоритм:
1⃣Инициализируйте список смежности для преобразования дерева в граф и множество для хранения листовых узлов. Используйте вспомогательный метод traverseTree для обхода дерева, чтобы построить граф и найти листовые узлы. В параметрах поддерживайте текущий узел, а также родительский узел. Если текущий узел является листом, добавьте его в множество. В списке смежности добавьте текущий узел в список соседей родительского узла и наоборот. Рекурсивно вызовите traverseTree для левого и правого дочернего узла текущего узла.
2⃣Инициализируйте переменную ans для подсчета количества хороших пар листовых узлов. Итеративно переберите каждый листовой узел в множестве. Запустите BFS для текущего листового узла. BFS можно прервать досрочно, как только будут обнаружены все узлы, находящиеся на расстоянии от текущего листового узла. Увеличьте ans для каждого листового узла, найденного в каждом запуске BFS.
3⃣Верните ans / 2. Мы считаем каждую пару дважды, поэтому нужно разделить на 2, чтобы получить фактическое количество.
😎 Решение:
class Solution {
function countPairs($root, $distance) {
$graph = [];
$leafNodes = new SplObjectStorage();
$this->traverseTree($root, null, $graph, $leafNodes);
$ans = 0;
foreach ($leafNodes as $leaf) {
$bfsQueue = new SplQueue();
$seen = new SplObjectStorage();
$bfsQueue->enqueue($leaf);
$seen->attach($leaf);
for ($i = 0; $i <= $distance; $i++) {
$size = $bfsQueue->count();
for ($j = 0; $j < $size; $j++) {
$currNode = $bfsQueue->dequeue();
if ($leafNodes->contains($currNode) && $currNode !== $leaf) {
$ans++;
}
if (isset($graph[spl_object_hash($currNode)])) {
foreach ($graph[spl_object_hash($currNode)] as $neighbor) {
if (!$seen->contains($neighbor)) {
$bfsQueue->enqueue($neighbor);
$seen->attach($neighbor);
}
}
}
}
}
}
return $ans / 2;
}
private function traverseTree($currNode, $prevNode, &$graph, $leafNodes) {
if ($currNode === null) {
return;
}
if ($currNode->left === null && $currNode->right === null) {
$leafNodes->attach($currNode);
}
if ($prevNode !== null) {
$graph[spl_object_hash($prevNode)][] = $currNode;
$graph[spl_object_hash($currNode)][] = $prevNode;
}
$this->traverseTree($currNode->left, $currNode, $graph, $leafNodes);
$this->traverseTree($currNode->right, $currNode, $graph, $leafNodes);
}
}Ставь 👍 и забирай 📚 Базу знаний