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

动态规划想法