1245. Tree Diameter

leetcode medium

#array#csharp#graph#hash-table#leetcode#medium#search#tree

Task

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

Пример:

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

Output: 2

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public int TreeDiameter(int[][] edges) {
        if (edges.Length == 0) return 0;
        var graph = new Dictionary<int, List<int>>();
        foreach (var edge in edges) {
            if (!graph.ContainsKey(edge[0])) graph[edge[0]] = new List<int>();
            if (!graph.ContainsKey(edge[1])) graph[edge[1]] = new List<int>();
            graph[edge[0]].Add(edge[1]);
            graph[edge[1]].Add(edge[0]);
        }
        int farthestNode = 0;
        int Dfs(int node, int parent) {
            int maxDepth = 0;
            foreach (var neighbor in graph[node]) {
                if (neighbor != parent) {
                    int depth = Dfs(neighbor, node);
                    if (depth + 1 > maxDepth) {
                        maxDepth = depth + 1;
                        farthestNode = neighbor;
                    }
                }
            }
            return maxDepth;
        }
        Dfs(0, -1);
        int startNode = farthestNode;
        Dfs(startNode, -1);
        return Dfs(farthestNode, -1);
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public int TreeDiameter(int[][] edges) {
        if (edges.size() == 0) return 0;
        var graph = new unordered_map<int, List<int>>();
        foreach (var edge in edges) {
            if (!graph.count(edge[0])) graph[edge[0]] = new List<int>();
            if (!graph.count(edge[1])) graph[edge[1]] = new List<int>();
            graph[edge[0]].push_back(edge[1]);
            graph[edge[1]].push_back(edge[0]);
        }
        int farthestNode = 0;
        int Dfs(int node, int parent) {
            int maxDepth = 0;
            foreach (var neighbor in graph[node]) {
                if (neighbor != parent) {
                    int depth = Dfs(neighbor, node);
                    if (depth + 1 > maxDepth) {
                        maxDepth = depth + 1;
                        farthestNode = neighbor;
                    }
                }
            }
            return maxDepth;
        }
        Dfs(0, -1);
        int startNode = farthestNode;
        Dfs(startNode, -1);
        return Dfs(farthestNode, -1);
    }
}

Java solution

matched/original

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);
    }
}

Python solution

matched/original

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

Explanation

Algorithm

Построение графа:

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

Поиск самой удаленной вершины (DFS1):

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

Поиск диаметра (DFS2):

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

Устанавливаем счет игрока в 0.

😎