1245. Tree Diameter

LeetCode medium original: C# #array #csharp #graph #hash-table #leetcode #medium #search #tree

選択した UI 言語に合わせて問題文をロシア語から翻訳します。コードは変更しません。

LeetCode Static

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

例:

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

Output: 2

C# 解法

照合済み/オリジナル

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++ 解法

自動ドラフト、提出前に確認

#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 解法

照合済み/オリジナル

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 解法

照合済み/オリジナル

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

Algorithm

Построение グラフа:

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

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

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

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

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

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

😎

Vacancies for this task

有効な求人 with overlapping task tags are 表示.

すべての求人

有効な求人はまだありません。