Minimum Height Trees

一道纠结很久的题，一开始想的朴素BFS方法，继而就发现这种朴素真BFS在图类型题中都不是很行得通（至今做的真图（以node label来指代结点，二元对来指代edge）里好像并没有真的有用纯BFS来解得），所谓图的BFS，更多时候是指出入度的BFS搜索，而这道题要想通就是两点

• 所谓的MHT到底在一个无环无向图中有几个？
• 我们应该如何通过出入度来进行BFS？

对于第一点，答案是最多两个，原因其实并不是很好解释，但是仔细思考一下就会发现是一个很自然的答案，非要举例的话，可以想想一个有树特性的图是必然有至少一个中心点的，而如果结点个数为偶数，则有可能存在两个中心点，这就跟数组的中位数一样的道理

对于第二点，这道题里用的方法是先统计只有一个入度的结点，只有一个入度代表此节点必为叶子节点，然后根据这些叶子节点，我们可以进一步找到连接这些叶子节点的结点，它们就是下一轮潜在的叶子节点，通过上述逻辑就可以清晰的看到一个BFS循环的存在了，下面只需要实现就行了，代码如下

class Solution(object):
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        if n <= 2:
            return [x for x in xrange(n)]

        ind = [set([]) for _ in xrange(n)]

        for st, ed in edges:
            ind[st].add(ed)
            ind[ed].add(st)

        lefts = [x for x in xrange(n) if len(ind[x]) == 1]

        while n > 2:
            n -= len(lefts)
            new_lefts = []
            for leave in lefts:
                tmp = ind[leave].pop()
                ind[tmp].remove(leave)
                if len(ind[tmp]) == 1:
                    new_lefts.append(tmp)
            lefts = new_lefts

        return lefts

改进了一下逻辑

class Solution(object):
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        ind = [set() for _ in xrange(n)]
        for st, ed in edges:
            ind[st].add(ed)
            ind[ed].add(st)

        lefts = [index for index, lst in enumerate(ind) if len(lst) <= 1]
        while n > 2:
            n -= len(lefts)
            tmpLefts = []
            for node in lefts:
                neigh = ind[node].pop()
                ind[neigh].remove(node)
                if len(ind[neigh]) == 1:
                    tmpLefts.append(neigh)
            lefts = tmpLefts[:]

        return lefts