The diameter of a tree is the number of edges in the longest path in that tree.
There is an undirected tree of n nodes labeled from 0 to n - 1. You are given a 2D array edges where edges.length == n - 1 and edges[i] = [ai, bi] indicates that there is an undirected edge between nodes ai and bi in the tree.
Return the diameter of the tree.
Example 1:
0
/ \
2 1
Input: edges = [[0,1],[0,2]]
Output: 2
Explanation: The longest path of the tree is the path 1 - 0 - 2.
Example 2:
1
/ | \
0 2 4
| |
3 5
Input: edges = [[0,1],[1,2],[2,3],[1,4],[4,5]]
Output: 4
Explanation: The longest path of the tree is the path 3 - 2 - 1 - 4 - 5.
Constraints:
n == edges.length + 11 <= n <= 1040 <= ai, bi < nai != bi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
|
'''
DFS
'''
from collections import defaultdict
class Solution:
def treeDiameter(self, edges: List[List[int]]) -> int:
graph = defaultdict(list)
for s, d in edges:
graph[s].append(d)
graph[d].append(s)
def dfs(node: int) -> int:
top_dis1, top_dis2 = 0, 0
visited.add(node)
dis = 0
for c in graph[node]:
if c not in visited:
dis = 1 + dfs(c)
if dis > top_dis1:
top_dis1, top_dis2 = dis, top_dis1
elif dis > top_dis2:
top_dis2 = dis
self.diameter = max(self.diameter, top_dis1 + top_dis2)
return top_dis1
self.diameter = 0
visited = set()
dfs(0)
return self.diameter
'''
2-time BFS
'''
class Solution:
def treeDiameter(self, edges: List[List[int]]) -> int:
graph = defaultdict(list)
for s, d in edges:
graph[s].append(d)
graph[d].append(s)
def bfs(node: int) -> Tuple[int, int]:
visited = set([node])
last_node = -1
dis = -1
q = [node]
while q:
temp_q = []
for n in q:
for child in graph[n]:
if child not in visited:
visited.add(child)
temp_q.append(child)
last_node = child
dis += 1
q = temp_q
return last_node, dis
far_node_1, dis_1 = bfs(0)
far_node_2, dis_2 = bfs(far_node_1)
return dis_2
|