Задача: 1245. Tree Diameter
Сложность: medium

Диаметр дерева - это количество ребер в самом длинном пути в этом дереве. Имеется неориентированное дерево из n узлов, помеченных от 0 до n - 1. Вам дан двумерный массив edges, где edges.length == n - 1 и edges[i] = [ai, bi] означает, что между узлами ai и bi в дереве есть неориентированное ребро. Верните диаметр дерева.

Пример:

Input: edges = [[0,1],[0,2]]
Output: 2

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

1⃣Построение графа:
Используем представление графа в виде списка смежности.

2⃣Поиск самой удаленной вершины (DFS1):
Запускаем DFS от произвольной вершины (например, 0) для нахождения самой удаленной вершины от нее.

3⃣Поиск диаметра (DFS2):
Запускаем DFS от найденной на предыдущем шаге самой удаленной вершины и находим самую удаленную вершину от нее. Это расстояние и будет диаметром дерева.reset(playerId):
Устанавливаем счет игрока в 0.

😎 Решение:

function treeDiameter($edges) {
    if (count($edges) === 0) return 0;

    $graph = [];
    foreach ($edges as $edge) {
        if (!isset($graph[$edge[0]])) $graph[$edge[0]] = [];
        if (!isset($graph[$edge[1]])) $graph[$edge[1]] = [];
        $graph[$edge[0]][] = $edge[1];
        $graph[$edge[1]][] = $edge[0];
    }

    $farthestNode = 0;

    function dfs($node, $parent, &$graph, &$farthestNode) {
        $maxDepth = 0;
        foreach ($graph[$node] as $neighbor) {
            if ($neighbor !== $parent) {
                $depth = dfs($neighbor, $node, $graph, $farthestNode);
                if ($depth + 1 > $maxDepth) {
                    $maxDepth = $depth + 1;
                    $farthestNode = $neighbor;
                }
            }
        }
        return $maxDepth;
    }

    dfs(0, -1, $graph, $farthestNode);
    $startNode = $farthestNode;

    dfs($startNode, -1, $graph, $farthestNode);
    return dfs($farthestNode, -1, $graph, $farthestNode);
}

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