310. Minimum Height Trees.md

310. Minimum Height Trees

思路

给定一个可以表示成树的无向图, 可知存在很多种表示法方法, 要求树高最小的树的根节点.

brute force思路就是从每个结点出发分别bfs把树高求出来, 然后返回树高最小的对应的根节点就行了. 但是这样要对每个结点进行bfs, 时间复杂度很高会超时.

思路一

题目给了一个提示: How many MHTs can a graph have at most? 稍加思考可以得出最多有两棵, 而且根节点就是直径(即距离最长的两个叶子间的距离)路径的中心结点, 如果直径为奇数那么只有一棵, 如果直径为偶数则有两棵. 所以我么可以先把这个直径求出来:

从任意点bfs到深度最大叶子，再从该叶子节点bfs到最远节点，第二遍bfs的时候记录每个点的父节点, 最后就可以得到直径路径, 然后返回直径路径的中心结点就行了.

时空复杂度为O(n)

思路二

上面的思路需要两次bfs. 其实此题还有个更加简便的方法求直径的中心结点:

• 去掉当前图的所有叶子节点，重复此操作直到只剩下一个或两个结点。

相当于是从最外面向内部进行dfs, 这个思路有点类似拓扑排序, 即题目210. Course Schedule II, 可 参考210题解中的bfs思路.

C++

思路一

class Solution {
private:
    vector<int>furthest_path_BFS(vector<vector<int>>&G, int start){
        /*
        从start开始bfs到深度最大叶子的一条路径
        */
        int n = G.size(), cur;
        vector<bool>visited(n, false);
        
        vector<int>path(n, -1); // path[i] = j 表示访问路径中节点j的父亲是i
        queue<int>q{{start}};
        
        while(!q.empty()){
            cur = q.front(); q.pop();
            visited[cur] = true;
            
            for(int i: G[cur]){
                if(!visited[i]){
                    q.push(i);
                    path[i] = cur;
                }
            }
        }
        // 此时cur就是bfs能到达的最远的节点之一
        vector<int>res;
        while(cur != -1){
            res.push_back(cur);
            cur = path[cur];
        }

        return res;
    }
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<vector<int>>G(n);
        
        for(auto &e: edges){
            G[e[0]].push_back(e[1]);
            G[e[1]].push_back(e[0]);
        }
        
        vector<int>tmp = furthest_path_BFS(G, 0);
        vector<int>diameter = furthest_path_BFS(G, tmp[0]); // 最长直径
                
        int d = diameter.size();
        if(d % 2) return {diameter[d/2]};
        return {diameter[d/2 - 1], diameter[d/2]};
    }
};

思路二

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<vector<int>>G(n, vector<int>());
        for(int i = 0; i < edges.size(); i++){
            G[edges[i][0]].push_back(edges[i][1]);
            G[edges[i][1]].push_back(edges[i][0]);
        }
        
        queue<int>leafs; // 存放当前所有叶子
        for(int i = 0; i < n; i++)
            if(G[i].size() <= 1) leafs.push(i);
        
        while(n > 2){
            int cur_size = leafs.size();
            n -= cur_size;
            while(cur_size--){
                int leaf = leafs.front(); leafs.pop();
                int to = G[leaf][0];
                for(int j = 0; j < G[to].size(); j++)
                    if(G[to][j] == leaf){
                        G[to].erase(G[to].begin()+j);
                        break;
                    }
                if(G[to].size() == 1) leafs.push(to);
            }
        }
        
        vector<int>res;
        while(!leafs.empty()){
            res.push_back(leafs.front());
            leafs.pop();
        }
        return res;
    }
};