题目
树是一个无向图，其中任何两个顶点只通过一条路径连接。 换句话说，任何一个没有简单环路的连通图都是一棵树。
给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [ai, bi]，表示树中节点 ai 和 bi 之间存在一条无向边（ai不等于bi）。
可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 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、将给定的边构建成邻接列表表示的图。
2、初始化一个队列，用于BFS。首先将所有度为1的节点（叶子节点）入队。
3、当队列非空时，进行以下操作：
（1）遍历当前层的所有节点，对于每个节点，将其父节点的度减1。如果其度变为1，则将该父节点加入队列。
（2）移除当前层的所有节点。
4、最后，队列中的节点即为所有可能的最小高度树的根节点。
根据上面的算法步骤，我们可以得出下面的示例代码。
from collections import defaultdict, deque
def minimum_height_tree_bfs(n, edges):
if n == 1:
return [0]
# 构建邻接列表表示的图
graph = defaultdict(list)
for edge in edges:
graph[edge[0]].append(edge[1])
graph[edge[1]].append(edge[0])
# 找到所有叶子节点并入队
leaves = [node for node in graph if len(graph[node]) == 1]
queue = deque(leaves)
while n > 2:
# 当前层节点数，即这一轮要移除的叶子节点数
current_level_size = len(queue)
n -= current_level_size
for _ in range(current_level_size):
# 出队当前层的节点
leaf = queue.popleft()
# 遍历该节点的邻居（只有一个邻居，因为是叶子节点）
for neighbor in graph[leaf]:
# 减少邻居的度数
graph[neighbor].remove(leaf)
# 如果邻居变成新的叶子节点，加入队列
if len(graph[neighbor]) == 1:
queue.append(neighbor)
# 队列中剩下的节点即为最小高度树的根
return list(queue)
print(minimum_height_tree_bfs(4, [[1, 0], [1, 2], [1, 3]]))
print(minimum_height_tree_bfs(6, [[3, 0], [3, 1], [3, 2], [3, 4], [5, 4]]))总结
广度优先搜索法的时间复杂度为O(n)，空间复杂度也为O(n)。广度优先搜索法在处理最小高度树的问题时，既高效又相对节省空间。尤其是在树结构平衡的情况下，队列中的元素数量会远小于n。其时间复杂度和空间复杂度都与树的节点数n成线性关系，这意味着算法的扩展性很好，能够有效处理大规模的树结构。
