xxx 最小高度树（Minimum Height Trees）问题

问题描述
给定一个具有 n 个节点的树（即无环连通无向图），以及一个从 0 到 n-1 的节点编号列表。树可以以任意节点为根形成有根树，此时从根到叶子的最长路径长度称为树的高度。最小高度树（MHT）是指所有可能的根节点中，树高度最小的那些根节点。要求找出所有这样的根节点。

关键观察

1. 树的中心性：最小高度树的根节点实际是树的“中心”，即图中最长路径（直径）的中点。
2. 拓扑排序思路：通过逐层剥离叶子节点（度为1的节点），最终剩下的1个或2个节点即为解。
3. 性质：树中最小高度树根节点最多有2个。若直径长度为偶数，有1个中心；若为奇数，有2个中心。

解题步骤

1. 边界处理

   • 若 n=1，直接返回 [0]；若 n=2，返回 [0,1]。

2. 构建邻接表与度数组

   • 使用邻接表存储树结构，同时记录每个节点的度（相邻节点数）。

3. 初始化叶子队列

   • 将所有度为1的节点（叶子）加入队列。

4. 层层剥离叶子

   • 当剩余节点数 > 2 时：
     a. 记录当前叶子层的节点数。
     b. 遍历当前所有叶子节点，将其从图中移除（度减为0）。
     c. 更新这些叶子的邻居节点的度。若邻居度降为1，加入下一轮叶子队列。
     d. 剩余节点数减去本层剥离的叶子数。

5. 返回剩余节点

   • 队列中剩余的1个或2个节点即为所有最小高度树的根节点。

示例说明
以 n=6, 边列表 [[0,1],[0,2],[0,3],[3,4],[3,5]] 为例：

1. 初始叶子：节点1、2、4、5（度=1）。
2. 第一轮：移除1、2、4、5，此时节点0度由4减为1，节点3度由3减为1。
3. 第二轮：移除节点0和3，剩余节点数为0，提前结束。最终返回 [0,3]？实际上应修正逻辑：当剩余节点≤2时终止，因此首轮移除后剩余节点0和3即为解。

算法特点

• 时间复杂度：O(n)，每个节点处理一次。
• 空间复杂度：O(n)，存储邻接表和队列。
• 核心思想：不断删除外层叶子，逐渐逼近中心节点。