Сложность: 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.
😎 Решение:
def treeDiameter(edges):
if not edges:
return 0
from collections import defaultdict
def dfs(node, parent):
max_depth = 0
for neighbor in graph[node]:
if neighbor != parent:
depth = dfs(neighbor, node)
if depth + 1 > max_depth:
max_depth = depth + 1
farthest_node[0] = neighbor
return max_depth
graph = defaultdict(list)
for a, b in edges:
graph[a].append(b)
graph[b].append(a)
farthest_node = [0]
dfs(0, -1)
start_node = farthest_node[0]
farthest_node = [0]
diameter = dfs(start_node, -1)
return diameter
Ставь 👍 и забирай 📚 Базу знаний