LeetCode 310. 最小高度树

◎

本节目标

逐层剥离树叶，保留使树高最小的一到两个中心节点。

这是图论综合中从树的外层向中心收缩的母题。根越靠近树的中心，到最远节点的距离越短。

查看 LeetCode 原题

题意与约束

给定一棵有 n 个节点的无向树，任选节点为根会得到不同高度，返回全部最小高度根。n == 1 时答案为 [0]；其他树最后只会留下一个或两个相邻中心。

直接思路与瓶颈

逐个节点作为根做一次 BFS/DFS 并计算最大深度，单次 O(n)、总计 O(n²)，对长链会重复扫描几乎相同的边。树的最远端一定是叶子，持续同时去掉所有叶子可以直接把问题缩到中心。

图模型与算法推导

用邻接表和 degree 记录无向树。初始把所有度为 1 的叶子入队；每轮固定当前队列大小，整体删除这一层叶子，递减相邻点度数，度数首次变为 1 的节点进入下一层。维护 remaining，直到剩余不超过两个节点。

正确性依据

叶子作为根必位于某条最长路径的端点，不可能比向内相邻节点更优。删除所有叶子等价于每条最长路径同时从两端缩短一条边，且不改变剩余节点之间的距离关系。重复此过程后留下的一或两个节点正是所有最长路径的中心，因此使最大距离最小。

样例执行过程

对边 [[1,0],[1,2],[1,3]]，初始度数为 [1,3,1,1]，叶子队列 [0,2,3]、剩余 4。本轮剥离三个叶子，节点 1 的度数依次为 2,1,0，在变为 1 时入队；剩余变为 1，停止并返回队列中的 [1]。这表示星形树的中心是 1。

代码实现

C++

C++17

#include <queue>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1) {
            return {0};
        }

        vector<vector<int>> graph(n);
        vector<int> degree(n, 0);
        for (const auto& edge : edges) {
            int first = edge[0];
            int second = edge[1];
            graph[first].push_back(second);
            graph[second].push_back(first);
            degree[first]++;
            degree[second]++;
        }

        queue<int> leaves;
        for (int vertex = 0; vertex < n; vertex++) {
            if (degree[vertex] == 1) {
                leaves.push(vertex);
            }
        }

        int remaining = n;
        while (remaining > 2) {
            int layerSize = static_cast<int>(leaves.size());
            remaining -= layerSize;
            for (int i = 0; i < layerSize; i++) {
                int leaf = leaves.front();
                leaves.pop();
                for (int nxt : graph[leaf]) {
                    degree[nxt]--;
                    if (degree[nxt] == 1) {
                        leaves.push(nxt);
                    }
                }
            }
        }

        vector<int> centers;
        while (!leaves.empty()) {
            centers.push_back(leaves.front());
            leaves.pop();
        }
        return centers;
    }
};

Python

Python 3

from collections import deque


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 first, second in edges:
            graph[first].append(second)
            graph[second].append(first)
            degree[first] += 1
            degree[second] += 1

        leaves = deque(vertex for vertex in range(n) if degree[vertex] == 1)
        remaining = n
        while remaining > 2:
            layer_size = len(leaves)
            remaining -= layer_size
            for _ in range(layer_size):
                leaf = leaves.popleft()
                for nxt in graph[leaf]:
                    degree[nxt] -= 1
                    if degree[nxt] == 1:
                        leaves.append(nxt)

        return list(leaves)

复杂度分析

每个节点至多入队一次、每条边至多从两端访问，时间 O(n)；邻接表、度数组和队列使用 O(n) 空间。

边界与易错点

• n == 1 没有度为 1 的叶子，需直接返回 [0]。
• 一轮必须先固定叶子数量，新叶子属于下一层。
• 停止于剩余不超过两个节点，不能把中心继续剥掉。
• 该结论依赖输入是树，不能直接套到一般无向图。

模式迁移

树中心、最小偏心率根或从外向内分层的问题可复用逐层剥叶；若要求具体最长路径或任意两点距离，则应选树形 DP 或两次遍历。