xxx 最小高度树（Minimum Height Trees）问题 问题描述 给定一个具有 n 个节点的树（即无环连通无向图），我们的目标是找到这棵树的"最小高度树"的根节点。换句话说，如果我们选择任意一个节点作为根节点，树的高度定义为从根节点到最远叶子节点的最长路径上的边数。最小高度树是指所有可能的根节点中，树高度最小的那些树。 输入 ：整数 n 表示节点数量（节点标签从 0 到 n-1 ），以及边列表 edges ，其中每个边 [u, v] 表示节点 u 和 v 之间的一条边。 输出 ：所有最小高度树的根节点列表。 示例 ： 输入： n = 4 , edges = [[1, 0], [1, 2], [1, 3]] 输出： [1] 解释：选择节点1作为根时，树的高度为1；选择其他节点作为根时，高度至少为2。 解题思路 这个问题可以通过"逐层剥离叶子节点"的方法高效解决。核心思想是：最小高度树的根节点实际上位于树的最长路径（直径）的中点。通过反复移除当前层的叶子节点（度数为1的节点），最终剩下的1个或2个节点即为所求。 详细步骤 步骤1：构建图的邻接表表示 使用邻接表来存储树结构，便于快速访问每个节点的邻居。 同时维护一个度数数组，记录每个节点当前的度数（即连接的边数）。 示例 （ n = 6 , edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]] ）： 邻接表： 0: [ 3 ] 1: [ 3 ] 2: [ 3 ] 3: [ 0, 1, 2, 4 ] 4: [ 3, 5 ] 5: [ 4 ] 度数数组： [1, 1, 1, 4, 2, 1] 步骤2：初始化叶子节点队列 将所有度数为1的节点（叶子节点）加入队列。 在示例中，初始叶子节点为： [0, 1, 2, 5] 步骤3：逐层剥离叶子节点 当剩余节点数 > 2 时，循环执行以下操作： 记录当前层的叶子节点数量。 遍历当前层的每个叶子节点： 将其从图中移除（即度数减至0，不再参与后续处理）。 更新其邻居节点的度数：邻居度数减1。 如果某个邻居节点度数减1后变为1，则将其加入下一轮的叶子节点队列。 剩余节点数减去当前层移除的叶子节点数。 示例执行过程 ： 第一层：移除叶子 [0, 1, 2, 5] 移除后，节点3的度数从4→0（实际计算中：4-3=1? 需逐步计算） 实际逐步计算： 移除0：3的度数4→3 移除1：3的度数3→2 移除2：3的度数2→1 → 此时3变为叶子，加入下轮队列 移除5：4的度数2→1 → 加入下轮队列 剩余节点： [3, 4] 第二层：移除叶子 [3, 4] 移除后无剩余节点，循环结束 步骤4：确定最终结果 当剩余节点数 ≤ 2 时，队列中剩余的节点即为最小高度树的根节点。 在示例中，最终剩余节点为 [3, 4] （但实际处理中会在第二层全部移除，最终无剩余？让我们重新验证）。 修正示例分析 ： 初始：n=6, 叶子[ 0,1,2,5 ] 第一层移除4个叶子后： 节点3度数原为4，被0,1,2连接，移除这三个后度数减为1（仅连4） 节点4度数原为2，被5连接后减为1（仅连3） 此时剩余节点[ 3,4 ]，且它们的度数都为1，成为新的叶子。 第二层移除3和4后，剩余节点数0，循环结束。 最终输出应为最后一轮处理前的剩余节点，即[ 3,4 ]。 算法实现要点 使用队列进行BFS式的分层剥离。 每轮剥离后，剩余节点数减少。 当剩余节点数≤2时，当前队列中的所有节点即为答案。 复杂度分析 时间复杂度：O(n)，每个节点和边仅被处理一次。 空间复杂度：O(n)，用于存储邻接表和度数数组。 总结 通过这种"拓扑排序"式的分层剥离，我们高效地找到了树的核心节点，这些节点作为根时能使树高度最小。这个方法避免了为每个节点计算高度的O(n²)暴力解法，是此类问题的经典优化方案。