题目
树是一个无向图,其中任何两个顶点只通过一条路径连接。 换句话说,任何一个没有简单环路的连通图都是一棵树。
给你一棵包含 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成线性关系,这意味着算法的扩展性很好,能够有效处理大规模的树结构。