310. 最小高度树 [medium]

https://leetcode-cn.com/problems/minimum-height-trees/

对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。

格式

该图包含 n 个节点，标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表（每一个边都是一对标签）。

你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边， [0, 1]和 [1, 0] 是相同的，因此不会同时出现在 edges 里。

示例 1:

输入: n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3 

输出: [1]

示例 2:

输入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5 

输出: [3, 4]

说明:

根据树的定义，树是一个无向图，其中任何两个顶点只通过一条路径连接。换句话说，一个任何没有简单环路的连通图都是一棵树。
树的高度是指根节点和叶子节点之间最长向下路径上边的数量。

通过次数8,869 | 提交次数26,064

First Try

2020-06-29

逆向的拓扑排序，跟之前DAG的BFS+indegree拓扑排序差不多，只不过是反着来。先寻找叶子节点，然后一圈圈往里面走，剥洋葱一样，一直到最后一层。这里面一个注意点是仍然需要按照level来执行，这样才能在最后一个level的时候捕捉到所有的节点。记得DAG的BFS+indegree是不需要识别level层级的。

依然是看题解才了解的思路，不过对BFS+indegree了解又加深了一层。

另外依然被一个低级bug困扰了许久，None和0在简易判断的额时候轻轻松松就混淆了，以后还是明确些好，谁知道遇到的是什么数据集。而且遇到超时的时候，在leetcode里还不能很快知道是否陷入死循环，还是只是自己写的算法复杂度不过关。

class Solution(object):
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        if not edges:
            return [0] # 这个特殊工况又没想到，又浪费一次提交
        graph = defaultdict(list)
        indegree = [0 for i in range(n)]
        for (curr, nex) in edges:
            graph[curr].append(nex)
            graph[nex].append(curr)
            indegree[curr] += 1
            indegree[nex] += 1
        
        leaves = []
        for idx in range(n):
            if indegree[idx] == 1:
                leaves.append(idx)
        # print(indegree)
        # print(leaves)
        leaves += [None]
        rv = []
        while(leaves):
            # if n - len(visited) <= 2:
            #     break
            node = leaves.pop(0)

            # 写成这样子竟然导致无限循环，可能因为node本身包括了0，wtf,又掉进一次坑
            # if leaves and not node:
            if node is None and len(leaves):
                rv = []
                leaves.append(None)  
                continue
            elif node is None:
                break
            rv.append(node)  # 无脑添加，总好过判断n=1或2

            for n in graph[node]:
                indegree[n] -= 1
                if indegree[n] == 1:
                    leaves.append(n)
            # if min(indegree) == 0:
            #     break        
        return rv
        

执行用时：240 ms, 在所有 Python 提交中击败了70.10%的用户
内存消耗：16.9 MB, 在所有 Python 提交中击败了100.00%的用户

Time Exceeded Version

2020-06-29

非常原始的方法，计算每个节点作为树根时候的高度，复杂度直接是O(n^2).在最后按顺序或是逆序排列的超大测试集的时候挂掉了。

class Solution(object):
    def findMinHeightTrees(self, n, edges):
        """
        :type n: int
        :type edges: List[List[int]]
        :rtype: List[int]
        """
        graph = collections.defaultdict(list)
        for curr, nex in edges:
            graph[curr].append(nex)
            graph[nex].append(curr)
        def dfs(node, cdep, maxdep, mindep, visited):
            visited.add(node)
            cdep += 1
            maxdep = max(maxdep, cdep)
            # print(node, cdep, maxdep)
            for n in graph[node]:
                if n in visited:
                    continue
                maxdep = max(maxdep, dfs(n, cdep, maxdep, mindep, visited))
                # 提前结束，把一个超长2s才算完的直接变成76ms,真有这么神奇么。。。
                # 但是如果最后一个点才是mindep,恶劣工况下依然没法通过才对啊
                # 果然还是超时了，在其他案例上
                if maxdep > mindep:
                    return float("inf") 
            # cdep -= 1
            return maxdep
        depth = dict()
        mindep = float("inf")
        for node in range(n):
            depth[node] = dfs(node, 0, 0, mindep, set())
            mindep = min(mindep, depth[node])
        # print(depth)
        rv = [k for k, v in depth.items() if v == mindep]
        return rv
            