310. 最小高度树
题目描述
树是一种连通且没有环的无向图，任意两个节点之间只有一条路径。
输入节点数 n，节点编号为 0 到 n - 1，以及包含 n - 1 条无向边的数组 edges，edges[i] = [ai, bi] 表示节点 ai 和 bi 相连。
可以挑任意一个节点当根。以某节点为根时，树的高度是从根往下走到叶子的最长路径上的边数。在所有选法中，高度最小的那些树称为最小高度树。
返回所有最小高度树的根节点编号，顺序不限。
示例 1
输入：n = 4, edges = [[1,0],[1,2],[1,3]] 输出：[1]
解释：节点 1 与其余三个点都直接相连，以 1 为根时高度为 1，这是唯一的最优根。
示例 2
输入：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]] 输出：[3,4]
解释：以 3 或 4 为根时高度都是 2，其他根都更高。
数据范围
1 <= n <= 2 * 10^4edges.length == n - 10 <= ai, bi < nai != bi- 所有
(ai, bi)两两不同。 - 输入保证构成一棵树，不含重复的边。
解题思路：拓扑排序（逐层剥离叶子）
最小高度树的根就是树的“中心”，即最长路径的中点。像剥洋葱一样从外往里削：每轮把当前所有叶子（度为 1 的节点）一起删掉，并更新邻居的度；邻居度变成 1 就成为下一轮的叶子。剩下不超过 2 个节点时，它们就是答案。
为什么正确
每轮同时删去所有叶子，剩下的树的中心不变；最长路径两端各缩短 1。
复杂度分析
时间 O(n)，空间 O(n)。
易错点
必须一轮一轮地删（按层），不能边删边把新叶子加入当前轮，否则会削过中心。n = 1 时没有叶子，要单独返回 [0]。循环条件是 remaining > 2，因为中心可能有 2 个。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
if n == 1:
return [0]
adj = [set() for _ in range(n)]
for a, b in edges:
adj[a].add(b)
adj[b].add(a)
leaves = [i for i in range(n) if len(adj[i]) == 1]
remaining = n
while remaining > 2:
remaining -= len(leaves)
new_leaves = []
for leaf in leaves:
nb = adj[leaf].pop()
adj[nb].remove(leaf)
if len(adj[nb]) == 1:
new_leaves.append(nb)
leaves = new_leaves
return leavesclass Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) {
return List.of(0);
}
List<Set<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) adj.add(new HashSet<>());
for (int[] e : edges) {
adj.get(e[0]).add(e[1]);
adj.get(e[1]).add(e[0]);
}
List<Integer> leaves = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (adj.get(i).size() == 1) leaves.add(i);
}
int remaining = n;
while (remaining > 2) {
remaining -= leaves.size();
List<Integer> newLeaves = new ArrayList<>();
for (int leaf : leaves) {
int nb = adj.get(leaf).iterator().next();
adj.get(leaf).clear();
adj.get(nb).remove(leaf);
if (adj.get(nb).size() == 1) {
newLeaves.add(nb);
}
}
leaves = newLeaves;
}
return leaves;
}
}class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
if (n == 1) {
return {0};
}
vector<unordered_set<int>> adj(n);
for (auto& e : edges) {
adj[e[0]].insert(e[1]);
adj[e[1]].insert(e[0]);
}
vector<int> leaves;
for (int i = 0; i < n; i++) {
if (adj[i].size() == 1) leaves.push_back(i);
}
int remaining = n;
while (remaining > 2) {
remaining -= leaves.size();
vector<int> newLeaves;
for (int leaf : leaves) {
int nb = *adj[leaf].begin();
adj[leaf].clear();
adj[nb].erase(leaf);
if (adj[nb].size() == 1) {
newLeaves.push_back(nb);
}
}
leaves = newLeaves;
}
return leaves;
}
};func findMinHeightTrees(n int, edges [][]int) []int {
if n == 1 {
return []int{0}
}
adj := make([]map[int]bool, n)
for i := range adj {
adj[i] = map[int]bool{}
}
for _, e := range edges {
adj[e[0]][e[1]] = true
adj[e[1]][e[0]] = true
}
leaves := []int{}
for i := 0; i < n; i++ {
if len(adj[i]) == 1 {
leaves = append(leaves, i)
}
}
remaining := n
for remaining > 2 {
remaining -= len(leaves)
newLeaves := []int{}
for _, leaf := range leaves {
nb := -1
for k := range adj[leaf] {
nb = k
}
delete(adj[leaf], nb)
delete(adj[nb], leaf)
if len(adj[nb]) == 1 {
newLeaves = append(newLeaves, nb)
}
}
leaves = newLeaves
}
return leaves
}var findMinHeightTrees = function(n, edges) {
if (n === 1) {
return [0];
}
const adj = Array.from({ length: n }, () => new Set());
for (const [a, b] of edges) {
adj[a].add(b);
adj[b].add(a);
}
let leaves = [];
for (let i = 0; i < n; i++) {
if (adj[i].size === 1) leaves.push(i);
}
let remaining = n;
while (remaining > 2) {
remaining -= leaves.length;
const newLeaves = [];
for (const leaf of leaves) {
const nb = adj[leaf].values().next().value;
adj[leaf].clear();
adj[nb].delete(leaf);
if (adj[nb].size === 1) {
newLeaves.push(nb);
}
}
leaves = newLeaves;
}
return leaves;
};function findMinHeightTrees(n: number, edges: number[][]): number[] {
if (n === 1) {
return [0];
}
const adj = Array.from({ length: n }, () => new Set<number>());
for (const [a, b] of edges) {
adj[a].add(b);
adj[b].add(a);
}
let leaves: number[] = [];
for (let i = 0; i < n; i++) {
if (adj[i].size === 1) leaves.push(i);
}
let remaining = n;
while (remaining > 2) {
remaining -= leaves.length;
const newLeaves: number[] = [];
for (const leaf of leaves) {
const nb = adj[leaf].values().next().value as number;
adj[leaf].clear();
adj[nb].delete(leaf);
if (adj[nb].size === 1) {
newLeaves.push(nb);
}
}
leaves = newLeaves;
}
return leaves;
}其他解法
拓扑剥离从外向内一层层删叶子，最后剩下的 1–2 个点就是中心，不需要显式找直径；两次 BFS 先找出直径再取中点。两者本质都是在找直径的中心，复杂度相同。
解法 2：两次 BFS 求直径取中点 时间 O(n)，空间 O(n)
最小高度树的根一定是树的最长路径（直径）的中点。先从任意节点 0 做 BFS 找到最远点 x，再从 x 做 BFS 找到最远点 y，并记录父节点，还原 x 到 y 的直径路径。路径点数为奇数时返回中间一个点，为偶数时返回中间两个点。
把问题转化成经典的树直径，结论清晰，只用两次普通 BFS。需要理解“两次 BFS 求直径”和“中心在直径中点”的证明，还要额外还原路径。
from collections import deque
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
adj = [[] for _ in range(n)]
for a, b in edges:
adj[a].append(b)
adj[b].append(a)
def bfs(src):
parent = [-1] * n
seen = [False] * n
seen[src] = True
q = deque([src])
last = src
while q:
last = q.popleft()
for v in adj[last]:
if not seen[v]:
seen[v] = True
parent[v] = last
q.append(v)
return last, parent
x, _ = bfs(0)
y, parent = bfs(x)
path = []
while y != -1:
path.append(y)
y = parent[y]
m = len(path)
if m % 2:
return [path[m // 2]]
return [path[m // 2 - 1], path[m // 2]]class Solution {
private List<Integer>[] adj;
private int[] parent;
private int bfs(int src, int n) {
Arrays.fill(parent, -1);
boolean[] seen = new boolean[n];
seen[src] = true;
Deque<Integer> q = new ArrayDeque<>();
q.offer(src);
int last = src;
while (!q.isEmpty()) {
last = q.poll();
for (int v : adj[last]) {
if (!seen[v]) {
seen[v] = true;
parent[v] = last;
q.offer(v);
}
}
}
return last;
}
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
adj = new List[n];
for (int i = 0; i < n; i++) adj[i] = new ArrayList<>();
for (int[] e : edges) {
adj[e[0]].add(e[1]);
adj[e[1]].add(e[0]);
}
parent = new int[n];
int x = bfs(0, n);
int y = bfs(x, n);
List<Integer> path = new ArrayList<>();
for (; y != -1; y = parent[y]) path.add(y);
int m = path.size();
if (m % 2 == 1) return List.of(path.get(m / 2));
return List.of(path.get(m / 2 - 1), path.get(m / 2));
}
}class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
vector<vector<int>> adj(n);
for (auto& e : edges) {
adj[e[0]].push_back(e[1]);
adj[e[1]].push_back(e[0]);
}
vector<int> parent(n);
auto bfs = [&](int src) {
fill(parent.begin(), parent.end(), -1);
vector<char> seen(n, 0);
seen[src] = 1;
queue<int> q;
q.push(src);
int last = src;
while (!q.empty()) {
last = q.front();
q.pop();
for (int v : adj[last]) {
if (!seen[v]) {
seen[v] = 1;
parent[v] = last;
q.push(v);
}
}
}
return last;
};
int x = bfs(0);
int y = bfs(x);
vector<int> path;
for (; y != -1; y = parent[y]) path.push_back(y);
int m = path.size();
if (m % 2) return {path[m / 2]};
return {path[m / 2 - 1], path[m / 2]};
}
};func findMinHeightTrees(n int, edges [][]int) []int {
adj := make([][]int, n)
for _, e := range edges {
adj[e[0]] = append(adj[e[0]], e[1])
adj[e[1]] = append(adj[e[1]], e[0])
}
parent := make([]int, n)
bfs := func(src int) int {
for i := range parent {
parent[i] = -1
}
seen := make([]bool, n)
seen[src] = true
q := []int{src}
last := src
for len(q) > 0 {
last = q[0]
q = q[1:]
for _, v := range adj[last] {
if !seen[v] {
seen[v] = true
parent[v] = last
q = append(q, v)
}
}
}
return last
}
x := bfs(0)
y := bfs(x)
path := []int{}
for ; y != -1; y = parent[y] {
path = append(path, y)
}
m := len(path)
if m%2 == 1 {
return []int{path[m/2]}
}
return []int{path[m/2-1], path[m/2]}
}var findMinHeightTrees = function(n, edges) {
const adj = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
adj[a].push(b);
adj[b].push(a);
}
const parent = new Array(n);
const bfs = (src) => {
parent.fill(-1);
const seen = new Array(n).fill(false);
seen[src] = true;
const q = [src];
let last = src;
for (let h = 0; h < q.length; h++) {
last = q[h];
for (const v of adj[last]) {
if (!seen[v]) {
seen[v] = true;
parent[v] = last;
q.push(v);
}
}
}
return last;
};
const x = bfs(0);
let y = bfs(x);
const path = [];
for (; y !== -1; y = parent[y]) path.push(y);
const m = path.length;
if (m % 2) return [path[m >> 1]];
return [path[m / 2 - 1], path[m / 2]];
};function findMinHeightTrees(n: number, edges: number[][]): number[] {
const adj: number[][] = Array.from({ length: n }, () => []);
for (const [a, b] of edges) {
adj[a].push(b);
adj[b].push(a);
}
const parent: number[] = new Array(n);
const bfs = (src: number): number => {
parent.fill(-1);
const seen: boolean[] = new Array(n).fill(false);
seen[src] = true;
const q: number[] = [src];
let last = src;
for (let h = 0; h < q.length; h++) {
last = q[h];
for (const v of adj[last]) {
if (!seen[v]) {
seen[v] = true;
parent[v] = last;
q.push(v);
}
}
}
return last;
};
const x = bfs(0);
let y = bfs(x);
const path: number[] = [];
for (; y !== -1; y = parent[y]) path.push(y);
const m = path.length;
if (m % 2) return [path[m >> 1]];
return [path[m / 2 - 1], path[m / 2]];
}