leetcode 310. Minimum Height Trees

程序员文章站 2022-04-27 08:52:00

...

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1 :

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

    0
    |
    1
   / \
  2   3 

Output: [1]

Example 2 :

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

 0  1  2
  \ | /
    3
    |
    4
    |
    5 

Output: [3, 4]

Note:

According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”
The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

找出以哪个节点为根节点时，树的高度最小。
首先想到的方法可能是枚举每一个点为根，在查询高度。但是这种做法重复的操作数太多，时间复杂度高。因而有没有更好的算法去解决这个问题？
先从这个根节点的特征下手。如果统计一下每个节点的入度，不难发现当节点的入度为1的时候，这个节点一定不会是最小高度树的根节点（ n==1 或 n==2 情况作为特殊情况判断）。排除了最外层的节点，那么所求的根节点必然在内部。对于没有分支的树
leetcode 310. Minimum Height Trees
所求的根节点就在内部，且处于对称中心最近的 3 和 4 节点。而推广到有分支的树时仍然时正确的。因此，问题转化为寻求距离树对称中心最近的节点。

我们也可以换一种更为直接的理解方式。要求树的高度，必然是从入度为 1 的节点出发，到当前假定的根节点，所经历的节点数即为以当前假定根节点为树的高度。因此我们可以从所有入度为 1 的节点出发，沿着给定的路径移动，直到相遇，或者彼此已经擦身而过一个节点的距离，此时的节点便是所求的最小高度树的根节点

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
        vector<int> ans;
        if(n==1){
            ans.push_back(0);
            return ans;
        }
        if(edges.size()==0)
            return ans;
        vector<int> deg(n,0);
        vector<vector<int> > preHead(n);
        for(const auto& pos : edges){
            preHead[pos.first].push_back(pos.second);
            deg[pos.first]++;
            preHead[pos.second].push_back(pos.first);
            deg[pos.second]++;
        }
        set<int> vis;
        queue<int> Q;
        for(register int i=0;i<n;i++)
            if(deg[i]==1){
                Q.push(i);
                vis.insert(i);
            }
        int now;
        while(!Q.empty()&&n>2){
            int len=Q.size();
            for(register int i=0;i<len;i++){
                now=Q.front();
                Q.pop();
                for(auto pos : preHead[now]){
                    deg[pos]--;
                    if(deg[pos]==1&&vis.find(pos)==vis.end()){
                        Q.push(pos);
                        vis.insert(pos);
                    }
                }
            }
            n-=len;
        }
        while(!Q.empty()){
            ans.push_back(Q.front());
            Q.pop();
        }
        return ans;
    }
};