bfs_leetcode 310 最小高度树
由于遍历每一个节点为根节点树的高度，再去求最小时间复杂度为O(n^2),超时
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
def find_height(node,result):
queue=collections.deque()
visit=[0 for _ in range(n)]
queue.append(node)
visit[node]=1
step=-1
while queue:
size=len(queue)
for _ in range(size):
x=queue.popleft()
for item in edges:
if item[0]==x and visit[item[1]]!=1:
queue.append(item[1])
visit[item[1]]=1
elif item[1]==x and visit[item[0]]!=1:
queue.append(item[0])
visit[item[0]]=1
step+=1
if step not in result:
result[step]=[node]
else:
result[step].append(node)
return result
minvalue=float('inf')
result={}
for i in range(n):
result=find_height(i,result)
for i in range(n):
if i in result.keys():
return result[i]所以反过来思考，从最外层向最里层遍历，也就是从叶子节点向根节点进行bfs,将出度为1的节点都入列，然后排除。最后当所有节点都在同一层，证明他们的高度都是一样的，所以均为答案。也就是当queue的长度等于当前没有遍历的剩余元素。
找到数的最小高度，那么就像层序遍历一样，从最外层一层一层往里数，当剩下的元素均在同一层时，这些元素就是最小层的元素了。而且是只剩下1，2个点，因为如果有多的点就会形成新的层。
具体实现方式和按层分组的层序遍历类似，先把最外层入队，然后每次循环队中全部元素。
找到这个元素未遍历过的相邻元素并入队。
直至一轮开始时剩余元素数量等于队中元素数量就不再遍历，因为这些就是全部能作为答案的元素了（也就是最中间层的元素）；
很显然，如果剩余元素比队中的多，那么说明还有元素没有遍历到，需要继续遍历；
剩余元素不会比队中的少，因为入队的元素是唯一且为剩余元素的。
作者：meng-li-ye-tian-xing
链接：https://leetcode-cn.com/problems/minimum-height-trees/solution/c-you-wai-zhi-nei-de-ceng-xu-bian-li-by-dnu8g/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
认识defaultdict：
from collections import defaultdict
当我使用普通的字典时，用法一般是dict={},添加元素的只需要dict[element] =value即，调用的时候也是如此，dict[element] = xxx,但前提是element字典里，如果不在字典里就会报错，如：
这时defaultdict就能排上用场了，defaultdict的作用是在于，当字典里的key不存在但被查找时，返回的不是keyError而是一个默认值。
defaultdict接受一个工厂函数作为参数
dict =defaultdict( factory_function)
这个factory_function可以是list、set、str等等，作用是当key不存在时，返回的是工厂函数的默认值，比如list对应[ ]，str对应的是空字符串，set对应set( )，int对应0。
注意：在这里使用了defaultdict,以及它的remove方法。
这个做法就是先将题目中的条件转为邻接矩阵，然后根据出度入队，然后在队列中和邻接矩阵中将遍历过的点进行删除，接着遍历当剩余未遍历的元素等于当前队列的元素，或者剩下的元素只有1-2个时返回结果，这其中deque()类型的结果需要转换成list。
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
neighbors=defaultdict(list)
queue=collections.deque()
visit=[0]*n
if n==1:
return [0]
for item in edges:
neighbors[item[0]].append(item[1])
neighbors[item[1]].append(item[0])
for key,value in neighbors.items():
if len(value)==1:
queue.append(key)
visit[key]=1
while queue:
size=len(queue)
if n==len(queue):
return list(queue)
for _ in range(size):
item=queue.popleft()
n-=1
nei=neighbors[item].pop()
neighbors[nei].remove(item)
if len(neighbors[nei])==1 and visit[nei]!=1:
queue.append(nei)
visit[nei]=1
递归方法，每次在一个点的邻接点中递归，通过记忆化减少时间复杂度，然后判断长度大小，将答案放入。
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
neighbors=defaultdict(list)
memo=defaultdict(list)
visit=[0]*n
ans=[]
for item in edges:
neighbors[item[0]].append(item[1])
neighbors[item[1]].append(item[0])
def dfs(start,visit,root):
key=start*1e5+root
if key in memo:
return memo[key]
visit[start]=1
ret=0
for i in neighbors[start]:
if visit[i]==1:
continue
ret=max(ret,dfs(i,visit,start))
memo[key]=ret+1
return ret+1
minvalue=float('inf')
for i in range(n):
visit=[0]*n
depth=dfs(i,visit,-1)-1
print(depth)
if depth<minvalue:
ans.clear()
ans.append(i)
minvalue=depth
elif depth==minvalue:
ans.append(i)
return ans
动态规划想法
怪不得普通人连面试的机会都没有 笑了