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

问题描述

给定一个包含 n 个节点的树（即一个无向、连通且无环的图），以及一个从 0 到 n-1 的节点编号。树可以看作是以任意节点为根的有根树。我们的目标是找到所有可能的根节点中，使得整棵树的高度最小的那些根节点。树的高度定义为从根到最远叶子节点的最长路径上的边数。返回一个列表，包含所有最小高度树的根节点编号。

示例

• 输入：n = 4, 边列表 edges = [[1,0],[1,2],[1,3]]
• 树的结构：

     0
     |
     1
    / \
   2   3
  

• 解释：以节点 1 为根时，树的高度为 1（最远叶子节点为 0、2 或 3）。以其他节点为根时，高度至少为 2。因此，最小高度树的根节点为 [1]。

解题思路

此问题的核心在于 “树的中心” 概念。对于一棵树，其所有最小高度树的根节点恰好是树的 中心 或 中心的两个节点（如果直径路径的节点数为偶数，则中心是一个节点；如果为奇数，则中心是两个相邻节点）。因此，问题转化为：找到树的直径，然后确定其中心节点。

但更直接且高效的解法是 “逐层剥离叶子节点”（拓扑排序思想），直到剩余 1 个或 2 个节点，这些节点即为所求的根节点。为什么？因为最小高度树的根节点一定位于树的“最中间”，即距离所有叶子节点最远的点（或两个点）。通过不断删除叶子节点（度为 1 的节点），我们最终会收敛到中心。

算法步骤（BFS 层序遍历）

1. 边界情况：如果 n <= 2，那么所有节点都是最小高度树的根节点，直接返回 [0, ..., n-1]。
2. 构建邻接表和度数组：
   • 使用邻接表表示树。
   • 记录每个节点的度（即相邻节点数）。
3. 初始化队列：
   • 将所有度为 1 的叶子节点加入队列。
4. 层序剥离：
   • 当剩余节点数 > 2 时，进行以下操作：
     a. 获取当前层的叶子节点数量 size。
     b. 对于队列中的每个叶子节点 leaf：
     • 将其从图中“移除”（减少剩余节点数）。
     • 遍历 leaf 的每个邻居 neighbor：
       • 将 neighbor 的度减 1。
       • 如果 neighbor 的度变为 1，则将其加入队列（作为下一层的叶子节点）。
         c. 处理完当前层后，剩余节点数更新。
5. 返回结果：
   • 当剩余节点数 <= 2 时，队列中剩余的节点即为所有最小高度树的根节点。

举例说明

以示例 n = 6, edges = [[0,1],[0,2],[0,3],[3,4],[3,5]] 为例：

树结构：
    1    2
     \  /
      0
       |
       3
      / \
     4   5

步骤：

1. 初始化：
   • 度数组：deg[0]=3, deg[1]=1, deg[2]=1, deg[3]=3, deg[4]=1, deg[5]=1
   • 叶子节点（度为 1）：[1,2,4,5]，加入队列。
   • 剩余节点数 remaining = 6。
2. 第一层剥离（remaining=6>2）：
   • 处理叶子 1,2,4,5：
     • 移除 1：邻居 0 的度从 3 减为 2。
     • 移除 2：邻居 0 的度从 2 减为 1（0 变为新叶子，加入队列）。
     • 移除 4：邻居 3 的度从 3 减为 2。
     • 移除 5：邻居 3 的度从 2 减为 1（3 变为新叶子，加入队列）。
   • 剩余节点：[0,3]，remaining=2。
3. 停止剥离（remaining<=2）：
   • 队列中剩余节点为 [0,3]，即为最小高度树的根节点。
   • 验证：以 0 或 3 为根，树的高度均为 2。

时间复杂度与空间复杂度

• 时间复杂度：O(n)，每个节点和每条边只被处理一次。
• 空间复杂度：O(n)，用于存储邻接表和队列。

代码实现（Python 风格伪代码）

def findMinHeightTrees(n, edges):
    if n <= 2:
        return list(range(n))
    
    # 构建邻接表和度数组
    adj = [[] for _ in range(n)]
    deg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
        deg[u] += 1
        deg[v] += 1
    
    # 初始化叶子队列
    leaves = deque([i for i in range(n) if deg[i] == 1])
    remaining = n
    
    # 层序剥离
    while remaining > 2:
        size = len(leaves)
        remaining -= size
        for _ in range(size):
            leaf = leaves.popleft()
            for neighbor in adj[leaf]:
                deg[neighbor] -= 1
                if deg[neighbor] == 1:
                    leaves.append(neighbor)
    
    return list(leaves)

总结

最小高度树问题通过 “逐层剥离叶子节点” 的方法，高效地找到了树的中心节点。这个算法基于树的性质：中心节点是距离所有叶子节点最远的点，通过反复删除叶子节点，最终会收敛到中心。此方法避免了复杂的直径计算，直接得到所有可能的最小高度树根节点。