LeetCode 第310题：最小高度树

📖 文章摘要

本文详细解析LeetCode第310题“最小高度树”，这是一道图论题目。文章提供了基于拓扑排序的解决方案，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能分析。适合对图论算法感兴趣的程序员。

核心知识点： 图论、拓扑排序、树的性质、BFS
难度等级： 中等
推荐人群： 具有基础数据结构知识，想要提升图论算法能力的程序员

题目描述

树是一个无向图，其中任何两个顶点只通过一条路径连接。换句话说，一个任何没有简单环路的连通图都是一棵树。

给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi] 表示树中节点 ai 和 bi 之间存在一条无向边。

可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为最小高度树。

请你找到所有的最小高度树并按任意顺序返回它们的根节点标签列表。

示例

示例 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]

示例2

提示

1 <= n <= 2 * 104
edges.length == n - 1
0 <= ai, bi < n
ai != bi
所有 (ai, bi) 互不相同
给定的输入保证是一棵树，并且不会有重复的边

解题思路

本题可以使用“剥洋葱”的方法来解决，即从外向内逐层删除叶子节点，最后剩下的1或2个节点就是最小高度树的根节点。

关键点：

最小高度树的根节点一定是整个图的“中心”
从叶子节点开始，逐层删除度为1的节点
最后剩下的1或2个节点即为答案

具体步骤：

构建邻接表表示图
计算每个节点的度数
将所有度为1的节点（叶子节点）加入队列
循环删除叶子节点，直到剩下1或2个节点
返回最后剩下的节点

图解思路

算法流程分析表

步骤	操作	数据结构	说明
初始化	构建图	邻接表	存储节点间的连接关系
计算度数	统计	数组	记录每个节点的度数
删除叶子	BFS	队列	逐层删除度为1的节点
获取结果	检查	列表	返回最后剩余的节点

节点删除过程分析表

轮次	删除节点	剩余节点	说明
初始	-	所有节点	原始状态
第一轮	叶子节点	非叶子节点	删除外层节点
最后	倒数第二层	1-2个中心节点	得到根节点

代码实现

C# 实现

public class Solution {
    public IList<int> FindMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return new List<int> { 0 };
        if (n == 2) return new List<int> { 0, 1 };
        
        // 构建邻接表
        var adj = new List<HashSet<int>>();
        for (int i = 0; i < n; i++) {
            adj.Add(new HashSet<int>());
        }
        
        // 填充邻接表并计算度数
        var degrees = new int[n];
        foreach (var edge in edges) {
            adj[edge[0]].Add(edge[1]);
            adj[edge[1]].Add(edge[0]);
            degrees[edge[0]]++;
            degrees[edge[1]]++;
        }
        
        // 初始化叶子节点队列
        var leaves = new Queue<int>();
        for (int i = 0; i < n; i++) {
            if (degrees[i] == 1) {
                leaves.Enqueue(i);
            }
        }
        
        // 剥洋葱过程
        var remainingNodes = n;
        while (remainingNodes > 2) {
            var leaveSize = leaves.Count;
            remainingNodes -= leaveSize;
            
            for (int i = 0; i < leaveSize; i++) {
                var leaf = leaves.Dequeue();
                foreach (var neighbor in adj[leaf]) {
                    adj[neighbor].Remove(leaf);
                    degrees[neighbor]--;
                    if (degrees[neighbor] == 1) {
                        leaves.Enqueue(neighbor);
                    }
                }
            }
        }
        
        return leaves.ToList();
    }
}

Python 实现

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]
        if n == 2:
            return [0, 1]
            
        # 构建邻接表
        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_nodes = n
        while remaining_nodes > 2:
            remaining_nodes -= len(leaves)
            new_leaves = []
            
            for leaf in leaves:
                neighbor = adj[leaf].pop()  # 获取叶子节点的唯一邻居
                adj[neighbor].remove(leaf)  # 从邻居节点移除叶子节点
                if len(adj[neighbor]) == 1:
                    new_leaves.append(neighbor)
                    
            leaves = new_leaves
            
        return leaves

C++ 实现

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1) return {0};
        if (n == 2) return {0, 1};
        
        // 构建邻接表
        vector<unordered_set<int>> adj(n);
        for (const auto& edge : edges) {
            adj[edge[0]].insert(edge[1]);
            adj[edge[1]].insert(edge[0]);
        }
        
        // 初始化叶子节点
        vector<int> leaves;
        for (int i = 0; i < n; i++) {
            if (adj[i].size() == 1) {
                leaves.push_back(i);
            }
        }
        
        // 剥洋葱过程
        int remainingNodes = n;
        while (remainingNodes > 2) {
            remainingNodes -= leaves.size();
            vector<int> newLeaves;
            
            for (int leaf : leaves) {
                int neighbor = *adj[leaf].begin();  // 获取叶子节点的唯一邻居
                adj[neighbor].erase(leaf);  // 从邻居节点移除叶子节点
                if (adj[neighbor].size() == 1) {
                    newLeaves.push_back(neighbor);
                }
            }
            
            leaves = move(newLeaves);
        }
        
        return leaves;
    }
};

执行结果

C# 实现

执行用时：128 ms
内存消耗：45.8 MB

Python 实现

执行用时：92 ms
内存消耗：19.2 MB

C++ 实现

执行用时：24 ms
内存消耗：24.6 MB

性能对比

语言	执行用时	内存消耗	特点
C#	128 ms	45.8 MB	性能适中，内存占用较大
Python	92 ms	19.2 MB	执行较快，内存占用适中
C++	24 ms	24.6 MB	执行最快，内存占用适中

代码亮点

🎯 使用“剥洋葱”方法巧妙解决最小高度树问题
💡 利用HashSet/Set实现O(1)的节点删除操作
🔍 优雅处理边界情况（n=1和n=2）
🎨 代码结构清晰，变量命名直观

常见错误分析

🚫 忽略特殊情况（n=1或n=2）
🚫 未正确维护节点的度数
🚫 错误处理节点删除过程
🚫 未考虑可能有多个根节点的情况

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
DFS遍历	O(n^2)	O(n)	直观易懂	效率低
剥洋葱法	O(n)	O(n)	效率高	实现复杂
最长路径	O(n)	O(n)	理论性强	不易实现

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新第310题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

图解思路

算法流程分析表

节点删除过程分析表

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流