⚡Flashcard Drill➔
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

  1. The minimum-height roots are the centres of the tree, found by repeatedly removing all leaves.
  2. A leaf is a node with degree 1. Peel them layer by layer; at most two nodes remain, and those are the centres.
  3. This is the same idea as finding the middle of a path, generalised to a tree.
  4. 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 <= 2 case: 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.
🎯 Drill This Card Now➔

🧩 Related Graphs Problems