LC: 1245. Tree Diameter
https://leetcode.com/problems/tree-diameter/
1245. Tree Diameter
Given an undirected tree, return its diameter: the number of edges in a longest path in that tree.
The tree is given as an array of edges where edges[i] = [u, v] is a bidirectional edge between nodes u and v. Each node has labels in the set {0, 1, ..., edges.length}.
Example 1:
Example 2:
Constraints:
0 <= edges.length < 10^4edges[i][0] != edges[i][1]0 <= edges[i][j] <= edges.lengthThe given edges form an undirected tree.
The Essence:
Ein Knoten n in diesem Baum ist mit k Knoten verbunden. Der Umfang des Baums in Bezug auf den Knoten n berechnet man durch Addition der Längen der zwei längsten Pfade durch zwei von diesen k Knoten. Man muss also der Umfang in Bezug auf jeden Knoten berechnen und dann mit dem vorher bestimmten Ergebnis vergleichen, um zu updaten.
Details:
Man kann dieses Verfahren rekursiv implementieren. In der entsprechen Tiefensuche muss den Elterknoten nicht zurück durchgelaufen werden. Das kann man durch ein Boolean-Array besucht[] oder einen extra Parameter machen.
Solution(s):
Default Code:
Last updated