LeetCode 310: Minimum Height Trees (Topological Leaf Trimming)
LeetCode 310GraphTopological BFSToday we solve LeetCode 310 - Minimum Height Trees.
Source: https://leetcode.com/problems/minimum-height-trees/
English
Problem Summary
Given an undirected tree with n nodes labeled 0..n-1, return all roots that produce trees with minimum height.
Key Insight
The root of a minimum height tree must be a center of the tree. If we repeatedly remove all current leaves (nodes with degree 1), we peel the tree layer by layer. The last remaining 1 or 2 nodes are exactly the centers.
Algorithm
- Build adjacency list and degree array.
- Push all leaves into queue.
- While remaining nodes > 2, remove one whole leaf layer and decrease neighbors' degree.
- Nodes left in queue are answers.
Complexity Analysis
Time: O(n).
Space: O(n).
Common Pitfalls
- Forgetting edge case n = 1 (answer is [0]).
- Removing leaves one-by-one without layer counting can break termination logic.
- Treating general graph as tree (input guarantees a tree).
Reference Implementations (Java / Go / C++ / Python / JavaScript)
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) return Arrays.asList(0);
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
int[] degree = new int[n];
for (int[] e : edges) {
int u = e[0], v = e[1];
graph.get(u).add(v);
graph.get(v).add(u);
degree[u]++;
degree[v]++;
}
Queue<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (degree[i] == 1) q.offer(i);
int remaining = n;
while (remaining > 2) {
int sz = q.size();
remaining -= sz;
for (int i = 0; i < sz; i++) {
int leaf = q.poll();
for (int nei : graph.get(leaf)) {
if (--degree[nei] == 1) q.offer(nei);
}
}
}
return new ArrayList<>(q);
}
}func findMinHeightTrees(n int, edges [][]int) []int {
if n == 1 {
return []int{0}
}
g := make([][]int, n)
deg := make([]int, n)
for _, e := range edges {
u, v := e[0], e[1]
g[u] = append(g[u], v)
g[v] = append(g[v], u)
deg[u]++
deg[v]++
}
q := make([]int, 0)
for i := 0; i < n; i++ {
if deg[i] == 1 {
q = append(q, i)
}
}
remain := n
for remain > 2 {
sz := len(q)
remain -= sz
nxt := make([]int, 0)
for _, leaf := range q {
for _, nei := range g[leaf] {
deg[nei]--
if deg[nei] == 1 {
nxt = append(nxt, nei)
}
}
}
q = nxt
}
return q
}class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
if (n == 1) return {0};
vector<vector<int>> g(n);
vector<int> degree(n, 0);
for (auto &e : edges) {
int u = e[0], v = e[1];
g[u].push_back(v);
g[v].push_back(u);
degree[u]++;
degree[v]++;
}
queue<int> q;
for (int i = 0; i < n; i++) if (degree[i] == 1) q.push(i);
int remaining = n;
while (remaining > 2) {
int sz = q.size();
remaining -= sz;
while (sz--) {
int leaf = q.front(); q.pop();
for (int nei : g[leaf]) {
if (--degree[nei] == 1) q.push(nei);
}
}
}
vector<int> ans;
while (!q.empty()) {
ans.push_back(q.front());
q.pop();
}
return ans;
}
};class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
if n == 1:
return [0]
graph = [[] for _ in range(n)]
degree = [0] * n
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
degree[u] += 1
degree[v] += 1
q = deque(i for i in range(n) if degree[i] == 1)
remaining = n
while remaining > 2:
size = len(q)
remaining -= size
for _ in range(size):
leaf = q.popleft()
for nei in graph[leaf]:
degree[nei] -= 1
if degree[nei] == 1:
q.append(nei)
return list(q)var findMinHeightTrees = function(n, edges) {
if (n === 1) return [0];
const g = Array.from({ length: n }, () => []);
const degree = new Array(n).fill(0);
for (const [u, v] of edges) {
g[u].push(v);
g[v].push(u);
degree[u]++;
degree[v]++;
}
let queue = [];
for (let i = 0; i < n; i++) {
if (degree[i] === 1) queue.push(i);
}
let remaining = n;
while (remaining > 2) {
remaining -= queue.length;
const next = [];
for (const leaf of queue) {
for (const nei of g[leaf]) {
degree[nei]--;
if (degree[nei] === 1) next.push(nei);
}
}
queue = next;
}
return queue;
};中文
题目概述
给定一棵无向树（节点编号 0..n-1），需要找出所有作为根时树高最小的节点。
核心思路
最小高度树的根一定是树的“中心”。不断删除当前所有叶子节点（度为 1），相当于从外向内一层层剥离。最后剩下的 1 或 2 个节点就是答案。
算法步骤
- 建图并统计每个节点度数。
- 把所有叶子节点入队。
- 当剩余节点数 > 2 时，每轮整层删除叶子，并更新邻居度数。
- 队列中最后剩余的节点即为最小高度树根。
复杂度分析
时间复杂度：O(n)。
空间复杂度：O(n)。
常见陷阱
- 忘记处理 n = 1 的边界情况，答案应为 [0]。
- 不按“层”删除叶子，导致终止条件判断混乱。
- 把一般图思路套到本题，实际上输入保证是树。
多语言参考实现（Java / Go / C++ / Python / JavaScript）
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) return Arrays.asList(0);
List<List<Integer>> graph = new ArrayList<>();
for (int i = 0; i < n; i++) graph.add(new ArrayList<>());
int[] degree = new int[n];
for (int[] e : edges) {
int u = e[0], v = e[1];
graph.get(u).add(v);
graph.get(v).add(u);
degree[u]++;
degree[v]++;
}
Queue<Integer> q = new ArrayDeque<>();
for (int i = 0; i < n; i++) if (degree[i] == 1) q.offer(i);
int remaining = n;
while (remaining > 2) {
int sz = q.size();
remaining -= sz;
for (int i = 0; i < sz; i++) {
int leaf = q.poll();
for (int nei : graph.get(leaf)) {
if (--degree[nei] == 1) q.offer(nei);
}
}
}
return new ArrayList<>(q);
}
}func findMinHeightTrees(n int, edges [][]int) []int {
if n == 1 {
return []int{0}
}
g := make([][]int, n)
deg := make([]int, n)
for _, e := range edges {
u, v := e[0], e[1]
g[u] = append(g[u], v)
g[v] = append(g[v], u)
deg[u]++
deg[v]++
}
q := make([]int, 0)
for i := 0; i < n; i++ {
if deg[i] == 1 {
q = append(q, i)
}
}
remain := n
for remain > 2 {
sz := len(q)
remain -= sz
nxt := make([]int, 0)
for _, leaf := range q {
for _, nei := range g[leaf] {
deg[nei]--
if deg[nei] == 1 {
nxt = append(nxt, nei)
}
}
}
q = nxt
}
return q
}class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
if (n == 1) return {0};
vector<vector<int>> g(n);
vector<int> degree(n, 0);
for (auto &e : edges) {
int u = e[0], v = e[1];
g[u].push_back(v);
g[v].push_back(u);
degree[u]++;
degree[v]++;
}
queue<int> q;
for (int i = 0; i < n; i++) if (degree[i] == 1) q.push(i);
int remaining = n;
while (remaining > 2) {
int sz = q.size();
remaining -= sz;
while (sz--) {
int leaf = q.front(); q.pop();
for (int nei : g[leaf]) {
if (--degree[nei] == 1) q.push(nei);
}
}
}
vector<int> ans;
while (!q.empty()) {
ans.push_back(q.front());
q.pop();
}
return ans;
}
};class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
if n == 1:
return [0]
graph = [[] for _ in range(n)]
degree = [0] * n
for u, v in edges:
graph[u].append(v)
graph[v].append(u)
degree[u] += 1
degree[v] += 1
q = deque(i for i in range(n) if degree[i] == 1)
remaining = n
while remaining > 2:
size = len(q)
remaining -= size
for _ in range(size):
leaf = q.popleft()
for nei in graph[leaf]:
degree[nei] -= 1
if degree[nei] == 1:
q.append(nei)
return list(q)var findMinHeightTrees = function(n, edges) {
if (n === 1) return [0];
const g = Array.from({ length: n }, () => []);
const degree = new Array(n).fill(0);
for (const [u, v] of edges) {
g[u].push(v);
g[v].push(u);
degree[u]++;
degree[v]++;
}
let queue = [];
for (let i = 0; i < n; i++) {
if (degree[i] === 1) queue.push(i);
}
let remaining = n;
while (remaining > 2) {
remaining -= queue.length;
const next = [];
for (const leaf of queue) {
for (const nei of g[leaf]) {
degree[nei]--;
if (degree[nei] === 1) next.push(nei);
}
}
queue = next;
}
return queue;
};
Comments