NeetCode #469LC-1245MediumTrees
← Back to All Problems#469 · #1245 · Tree Diameter(树的直径)
📌 Problem Statement & Constraints
Given an undirected tree represented as a list of
edges, return its diameter: the number of edges on the longest path between any two nodes. Constraints: 1 <= number of nodes <= 10^4, edges.length == number of nodes - 1.💡 Core Algorithmic Approaches
- Root the tree arbitrarily (at node 0) and compute, for each node, the two largest depths among its children.
- The longest path through a node is the sum of those two depths.
- Track the maximum over all nodes.
- This is the same idea as the binary-tree diameter, adapted to an adjacency list with a parent guard.
💻 Benchmark Python3 Implementation
class Solution:
def treeDiameter(self, edges: List[List[int]]) -> int:
from collections import defaultdict
g = defaultdict(list)
for a, b in edges:
g[a].append(b)
g[b].append(a) # undirected
self.best = 0
def dfs(node: int, parent: int) -> int:
top1 = top2 = 0
for c in g[node]:
if c == parent:
continue # do not go back up
d = dfs(c, node)
if d > top1:
top1, top2 = d, top1
elif d > top2:
top2 = d
self.best = max(self.best, top1 + top2)
return top1 + 1
if edges:
dfs(0, -1)
return self.best⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each node and edge is visited once.
💾 Space Complexity
O(n) for the adjacency list plus O(h) for the recursion.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the
parentguard: the DFS would loop forever on an undirected graph. - Summing all child depths: only the two deepest matter.
- Handling the single-node case: with no edges the diameter is 0, which the
if edgesguard returns. - Assuming the tree is a path: the two-deepest-children technique handles arbitrary branching.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.