NeetCode #601LC-310MediumGraphsNC 250
← Back to All Problems#601 · #310 · Minimum Height Trees(最小高度树)
📌 Problem Statement & Constraints
A tree is an undirected graph with no cycles. Given a tree of
n nodes labelled 0..n-1 and edges, return all labels that can be roots of a minimum height tree, in any order. Constraints: 1 <= n <= 2 * 10^4, edges.length == n - 1.💡 Core Algorithmic Approaches
- The minimum-height roots are the centres of the tree, found by repeatedly removing all leaves.
- A leaf is a node with degree 1. Peel them layer by layer; at most two nodes remain, and those are the centres.
- This is the same idea as finding the middle of a path, generalised to a tree.
- The alternative of computing the height for every root is O(n^2).
💻 Benchmark Python3 Implementation
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
if n <= 2:
return list(range(n)) # every node is a centre
from collections import defaultdict, deque
g = defaultdict(set)
for a, b in edges:
g[a].add(b)
g[b].add(a)
leaves = deque(node for node in g if len(g[node]) == 1)
remaining = n
while remaining > 2:
remaining -= len(leaves) # peel this whole layer
for _ in range(len(leaves)):
leaf = leaves.popleft()
for nxt in g[leaf]:
g[nxt].discard(leaf) # remove the edge
if len(g[nxt]) == 1:
leaves.append(nxt) # it just became a leaf
return list(leaves)⚡ Complexity Deep Dive
⏱️ Time Complexity
O(V + E): each node is peeled once.
💾 Space Complexity
O(V + E) for the adjacency structure.
⚠️ Interview Pitfalls & Follow-ups
- Computing the height from every node: O(V^2).
- Peeling one leaf at a time instead of a whole layer: the layer-based peeling is what keeps the centres correct.
- Forgetting the
n <= 2case: both nodes are centres, and the loop would not run correctly. - Removing the leaf from its own adjacency set: only the neighbour's set needs updating.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.