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

😎 Решение:

import java.util.*;

public class Solution {
    public int treeDiameter(int[][] edges) {
        if (edges.length == 0) return 0;

        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] edge : edges) {
            graph.computeIfAbsent(edge[0], k -> new ArrayList<>()).add(edge[1]);
            graph.computeIfAbsent(edge[1], k -> new ArrayList<>()).add(edge[0]);
        }

        int[] farthestNode = new int[1];

        int dfs(int node, int parent) {
            int maxDepth = 0;
            for (int neighbor : graph.get(node)) {
                if (neighbor != parent) {
                    int depth = dfs(neighbor, node);
                    if (depth + 1 > maxDepth) {
                        maxDepth = depth + 1;
                        farthestNode[0] = neighbor;
                    }
                }
            }
            return maxDepth;
        }

        dfs(0, -1);
        int startNode = farthestNode[0];

        dfs(startNode, -1);
        return dfs(farthestNode[0], -1);
    }
}

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