LC 1245 [M] Tree Diameter - ALawliet/algorithms GitHub Wiki
convert list of edges graph to tree, then is just "diameter of n-ary tree", but since it is graph also need to check for cycles like "graph valid tree"
class Solution:
def treeDiameter(self, edges: List[List[int]]) -> int:
# convert the given edges to a graph tree
tree = {i: [] for i in range(len(edges) + 1)}
for u, v in edges:
tree[u].append(v)
tree[v].append(u)
def dfs(node, parent): # we need to store and in the parent like "graph valid tree" to check for cycles
max1, max2 = 0, 0
for neighbor in tree.get(node):
if neighbor == parent: # cycle
continue
diameter = dfs(neighbor, node)
# graph is like n-ary tree, where we have more than just left and right so only want to check the 2 biggest
if max1 < max2:
max1 = max(max1, diameter)
else:
max2 = max(max2, diameter)
self.diameter = max(self.diameter, max1 + max2)
return max(max1, max2) + 1
self.diameter = 0
dfs(0, None)
return self.diameter