General Tree Diameter¶
Table of Contents¶
- 2246. Longest Path With Different Adjacent Characters (Hard)
- 3203. Find Minimum Diameter After Merging Two Trees (Hard)
- 1617. Count Subtrees With Max Distance Between Cities (Hard)
- 2538. Difference Between Maximum and Minimum Price Sum (Hard)
- 1245. Tree Diameter (Medium) 👑
- 3313. Find the Last Marked Nodes in Tree (Hard) 👑
2246. Longest Path With Different Adjacent Characters¶
3203. Find Minimum Diameter After Merging Two Trees¶
1617. Count Subtrees With Max Distance Between Cities¶
2538. Difference Between Maximum and Minimum Price Sum¶
1245. Tree Diameter¶
from collections import defaultdict, deque
from typing import List
# Tree Diameter
def treeDiameter(edges: List[List[int]]) -> int:
graph = defaultdict(list)
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
visited = {0}
q = deque([0])
cur = 0
while q:
size = len(q)
for _ in range(size):
cur = q.popleft()
for nxt in graph[cur]:
if nxt not in visited:
q.append(nxt)
visited.add(nxt)
visited = {cur}
q = deque([cur])
res = -1
while q:
size = len(q)
for _ in range(size):
cur = q.popleft()
for nxt in graph[cur]:
if nxt not in visited:
q.append(nxt)
visited.add(nxt)
res += 1
return res
edges = [[0, 1], [1, 2], [2, 3], [1, 4], [4, 5]]
assert treeDiameter(edges) == 4