leetcode 310 最小高度树(拓扑排序变形)

题目描述:

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

题解:

  首先要确定一个结论,最小高度树最多只有两个。可以用反证法证明,假设有n(n>=3)个最小高度树,那么这三个树的高度要一致。在这三个节点相邻的情况下(不相邻的情况一定不存在,可以推一下),分别取这三个节点为根节点的树的高度不一致,与假设相悖。

  再就是有向图的一个拓扑排序:

  step1:把度为1的点去掉(注意,一次操作需要把所有度为1的点去掉)

  step2:重复step1,直到剩下的节点个数小于等于2

 

AC代码:

  

class Solution {
public:
    // 
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        for(int i=0;i<n;i++)
        {
            edge[i].clear();
            degree[i] = 0;
        }
        int edge_Len = edges.size();
        for(int i=0;i<edge_Len;i++)
        {
            edge[edges[i][0]].push_back(edges[i][1]);
            edge[edges[i][1]].push_back(edges[i][0]);
            degree[edges[i][0]]++;
            degree[edges[i][1]]++;
        }

        vector<int> ans;
        queue<int> que;
        for(int i=0;i<n;i++)
        {
            if(degree[i] == 1 || degree[i] == 0) que.push(i);
        }
        int cnt = n;
        // 剩余节点的个数
        while(cnt>2)
        {
            // 把所有度为1的点都处理掉
            while(!que.empty())
            {
                int now = que.front();
                que.pop();
                cnt--;
                degree[now] = -1;
                int Len  = edge[now].size();
                for(int i=0;i<Len;i++)
                {
                    int next= edge[now][i];
                    degree[next]--;
                }
            }
            for(int i=0;i<n;i++)
            {
                if(degree[i] == 1 || degree[i] == 0) que.push(i);
            }
        }
        while(!que.empty())
        {
            int now = que.front();
            que.pop();
            ans.push_back(now);
        }
        return ans;
    }

private:
    vector<int> edge[10010];
    int degree[10010];
    
}; 

 

上一篇:[LeetCode] 310. Minimum Height Trees


下一篇:【精】数据结构与基础算法,容易弄明白