Задача: 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.

😎 Решение:

class Solution {
    func treeDiameter(_ edges: [[Int]]) -> Int {
        if edges.isEmpty { return 0 }

        var graph = [Int: [Int]]()
        for edge in edges {
            graph[edge[0], default: []].append(edge[1])
            graph[edge[1], default: []].append(edge[0])
        }

        var farthestNode = 0

        func dfs(_ node: Int, _ parent: Int) -> Int {
            var maxDepth = 0
            for neighbor in graph[node]! {
                if neighbor != parent {
                    let depth = dfs(neighbor, node)
                    if depth + 1 > maxDepth {
                        maxDepth = depth + 1
                        farthestNode = neighbor
                    }
                }
            }
            return maxDepth
        }

        _ = dfs(0, -1)
        let startNode = farthestNode

        _ = dfs(startNode, -1)
        return dfs(farthestNode, -1)
    }
}

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