Leetcode310:最小高度树
目录
题目
https://leetcode-cn.com/problems/minimum-height-trees/
这是一道理论性很强,代码也很有技巧性的“中等”难度题目。
题解
暴力法
献上我的超时代码:
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
find = {}
for edge in edges:
if edge[0] in find.keys():
find[edge[0]].append(edge[1])
else:
find[edge[0]] = [edge[1]]
if edge[1] in find.keys():
find[edge[1]].append(edge[0])
else:
find[edge[1]] = [edge[0]]
if not len(find):
return [0]
def findlevel(edges, root):
que = [root]
used = []
cnt = 0
while(len(que)):
# print(que)
for i in range(len(que)):
root = que.pop(0)
used.append(root)
for f in find[root]:
if f not in used:
que.append(f)
cnt+=1
return cnt-1
res_num = [findlevel(edges, root) for root in range(n)]
min_num = min(res_num)
return [i for i in range(len(res_num)) if res_num[i]==min_num]
广度优先搜索
有如下结论:
用反证法证明,证明过程挺复杂的。
所以我们就把这题从寻找最短距离变成了寻找最长距离。然后把路径记录下来,路径的中点就是我们要找的根节点。
你不觉得这个结论很奇妙吗?我想到了一团乱的绳子,如果你从中间把这堆绳子拎起来,四周绳子的末梢就会垂下去…
这题代码我分段详解:
首先是第一段代码:
g = [[] for _ in range(n)]
for x, y in edges:
g[x].append(y)
g[y].append(x)
parents = [0] * n
因为后面要在edges
里面查找某个节点连接的另一个节点,所以这里第一步先是做了一个初始化,便于后面的查询。最后得到的结果是g[x]=[a,b,c...]
,表示标号为x
的节点,连接了a,b,c等节点。(在我的代码中也有类似处理,但我用的是字典)
第二段:
def bfs(start: int):
vis = [False] * n
vis[start] = True
q = deque([start])
while q:
x = q.popleft()
for y in g[x]:
if not vis[y]:
vis[y] = True
parents[y] = x
q.append(y)
return x
x = bfs(0) # 找到与节点 0 最远的节点 x
y = bfs(x) # 找到与节点 x 最远的节点 y
这是一个用队列实现的广度优先搜索。vis
是记录已搜索过的节点。deque
是双向队列(震惊!原来python也是有数据结构的,我才知道😂)。parents
记录每个节点的父节点,用于下面找路径。
然后从0开始,找到最远节点x,再从x找最远节点y。那么x,y之间的距离就是最远的(这很奇妙)。
第三段:
path = []
parents[x] = -1
while y != -1:
path.append(y)
y = parents[y]
m = len(path)
return [path[m // 2]] if m % 2 else [path[m // 2 - 1], path[m // 2]]
在这里要找路径了,这时候parents
就派上用场了。如果找到路径长度为奇数,那么正中间那个数就是我们要找的根节点。如果路径长度为偶数,中间的数有两个,那么两个都是我们要找的根节点。
其他解法
这题还有深度优先搜索(跟广度优先搜索差不多),拓扑序列,不断剔除度为1的节点等方法,我太懒了,不想研究了…