310.md

310 Minimum Height Trees

Description

link

---

Solution BFS

这其实是一道BFS的题目，主要目的在于寻找最矮树的根节点

利用的一个巧妙的点在于如果一个节点只有一个度数（无向图）的话，那么它就是叶子节点，一个简单的想法就是从叶子节点出发不断向上寻找直到最后两个根节点遇到或者只有一步就可以停下来为止（n<2），如果途中两个相同的点遇到了，只保留一个即可（放在newleaves里面），这样找到的一定是最矮树（至于为什么需要数学证明）

---

Code

Complexity T : O(n) M : O(n)

class Solution:
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        if n == 1:
            return [0]
        
        paths = [set() for _ in range(n)]
        for i,j in edges:
            paths[i].add(j)
            paths[j].add(i)
        
        leaves = [i for i in range(n) if len(paths[i]) == 1]
        while n > 2:
            newleaves = []
            n -= len(leaves)
            for i in leaves:
                j = paths[i].pop()
                paths[j].remove(i)
                if len(paths[j]) == 1:
                    newleaves.append(j)
            leaves = newleaves
        return leaves