最小高度树

难度: Medium

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

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

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

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

树的高度是指根节点和叶子节点之间最长向下路径上边的数量。

示例 1：

输入：n = 4, edges = [[1,0],[1,2],[1,3]]
输出：[1]
解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。

示例 2：

输入：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
输出：[3,4]

提示：

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

Submission

运行时间: 72 ms

内存: 23.6 MB

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]
        g = [[] for _ in range(n)]
        degree = [0]*n
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
            degree[a] += 1
            degree[b] += 1
        q = deque(i for i in range(n) if degree[i] == 1)
        ans = []
        while q:
            ans.clear()
            for _ in range(len(q)):
                a = q.popleft()
                ans.append(a)
                for b in g[a]:
                    degree[b] -= 1
                    if degree[b] == 1:
                        q.append(b)
        return ans

Explain

该题解使用了BFS的思想。首先构建无向图的邻接表表示，并统计每个节点的度。然后将所有度为1的节点入队，每轮迭代中，将当前队列中的节点出队，更新其邻居节点的度，如果邻居节点的度变为1，则将其入队。最后一轮迭代得到的节点就是最小高度树的根节点。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 1:
            return [0]
        
        # 构建无向图的邻接表表示
        g = [[] for _ in range(n)]
        # 统计每个节点的度
        degree = [0]*n
        
        for a, b in edges:
            g[a].append(b)
            g[b].append(a)
            degree[a] += 1
            degree[b] += 1
        
        # 将所有度为1的节点入队
        q = deque(i for i in range(n) if degree[i] == 1)
        ans = []
        
        # BFS
        while q:
            ans.clear()
            for _ in range(len(q)):
                a = q.popleft()
                ans.append(a)
                # 更新a的邻居节点的度
                for b in g[a]:
                    degree[b] -= 1
                    if degree[b] == 1:
                        q.append(b)
                        
        return ans

Explore

在寻找最小高度树的过程中，从所有度为1的节点（叶子节点）开始进行BFS有助于从树的外围向中心收缩。这种方式可以逐步剥离最外层的叶子节点，直到剩下的节点无法再继续剥离（通常是中心节点或中心连线），这些剩余的节点就是最小高度树的可能的根节点。从叶子节点开始可以有效避免选择较长分支的顶端，从而确保树的高度尽可能小。

这种从外围向中心压缩的BFS操作通常被称为层次剥离法（Layer Peeling）或拓扑排序。在图理论中，这种方法经常用于寻找图的核心或中心层，特别适用于解决最小高度树（Minimum Height Trees）问题。这种方法通过逐层削减叶子节点，逼近图的中心，最终找到使得树高度最小的根节点。

通过逐渐剥离每层的叶子节点，直到不能再剥离为止，最后剩下的一层或几个节点就是图的中心层。这些节点是最后无法被进一步剥离的节点，因为它们互相连接，形成图的核心。在树或图的结构中，这些核心节点位于所有可能路径的大致中间点，因此从这些节点生成的树将具有最小的高度。这是因为从核心向外延伸的路径长度大致相等，从而保证了树的高度最小。

在构建无向图的邻接表和度数组时，理论上应该避免重复边和自环，因为它们可能会影响度的计算和BFS的正确性。在实现时，可以通过检查在添加边之前是否已经存在相同的边来避免重复边。对于自环，通常在无向图或树的结构中不应存在，如果输入数据包含自环，应该在读入数据时予以忽略或报错，因为自环在树的结构中没有实际意义。