leetcode310. 最小高度树/拓扑排序

119 阅读 0 评论 79 点赞

我是靠谱客的博主能干手套，这篇文章主要介绍leetcode310. 最小高度树/拓扑排序，现在分享给大家，希望可以做个参考。

文章目录

- 题目：310. 最小高度树
- 基本思想：bfs

题目：310. 最小高度树

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

格式

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

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

示例 1:

复制代码

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

        0
        |
        1
       / 
      2   3 

输出: [1]

示例 2:

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
输入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
       | /
        3
        |
        4
        |
        5 

输出: [3, 4]

说明:

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-height-trees
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

基本思想：bfs

先来说下这道题：题目中给的图的结构一定能够转化成一棵树，并且可以以任何一个节点为根（看题目要求），所谓最小高度树就是以图中每一个节点为根的树的最长路径（树的高度）中最短的

暴力思想：求以每一个节点为根的树的高度，可以bfs，也可以dfs，这两种思想都超时了，就不再给出代码了。

巧妙思想：一层一层删除度为1的节点，节点删除了，对应的边也递减，当剩下的节点不超过两个节点时，就是结果。这里有点像拓扑排序。

复制代码

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if(edges.size() == 0)
            return {0};
        vector<vector<int>> graph(n);
        vector<int> degree(n, 0);
        for(auto e : edges){
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
            ++degree[e[0]];
            ++degree[e[1]];
        }
        queue<int> q;
        int cnt = n;
        for(int i = 0; i < n; ++i){
            if(degree[i] == 1){
                degree[i] = 0;
                q.push(i);
            }
        }
        while(cnt > 2){
            int num = q.size();
            cnt -= num;
            while(num--){
                int t = q.front();
                q.pop();
                for(int i = 0; i < graph[t].size(); ++i){
                    if(degree[graph[t][i]] != 0){
                        degree[graph[t][i]]--;
                        if(degree[graph[t][i]] == 1){
                            degree[graph[t][i]] = 0;
                            q.push(graph[t][i]);
                        }
                    }
                }
                
            }
        }
        vector<int> res;
        while(!q.empty()){
            res.push_back(q.front());
            q.pop();
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if(edges.size() == 0)
            return {0};
        vector<vector<int>> graph(n);
        vector<int> degree(n, 0);
        for(auto e : edges){
            graph[e[0]].push_back(e[1]);
            graph[e[1]].push_back(e[0]);
            ++degree[e[0]];
            ++degree[e[1]];
        }
        queue<int> q;
        int cnt = n;
        for(int i = 0; i < n; ++i){
            if(degree[i] == 1){
                degree[i] = 0;
                q.push(i);
            }
        }
        while(cnt > 2){
            int num = q.size();
            cnt -= num;
            while(num--){
                int t = q.front();
                q.pop();
                for(int i = 0; i < graph[t].size(); ++i){
                    if(degree[graph[t][i]] != 0){
                        degree[graph[t][i]]--;
                        if(degree[graph[t][i]] == 1){
                            degree[graph[t][i]] = 0;
                            q.push(graph[t][i]);
                        }
                    }
                }
                
            }
        }
        vector<int> res;
        while(!q.empty()){
            res.push_back(q.front());
            q.pop();
        }
        return res;
    }
};