美文网首页
2020-10-21:最小高度树

2020-10-21:最小高度树

作者: Celia_QAQ | 来源:发表于2020-11-05 09:02 被阅读0次

    310:最小高度树

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

    格式
    该图包含 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]

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

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


    参考答案(谢谢大佬)

    public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n == 1)
            return { 0 };
        else if (n == 2)
            return{ 0,1 };
    
        vector<int> indegree(n,0);//入度数组,并初始化
        vector<int> v;
        vector<vector<int>> graph(n,v);//图形表示,并初始化
        for (int i = 0; i < edges.size(); i++)//构造图与入度数组:无向图,两个点都要处理
        {
            graph[edges[i][0]].push_back(edges[i][1]);
            graph[edges[i][1]].push_back(edges[i][0]);
            indegree[edges[i][0]]++;
            indegree[edges[i][1]]++;
        }
        queue<int> myqueue;//装载入度为1的queue
        for (int i = 0; i < n; i++)
        {
            if (indegree[i] == 1)
                myqueue.push(i);
        }
        int cnt = myqueue.size();//!!令cnt等于myqueue.size(),一次性将入度为1的点全部删去。
        while (n>2)
        {
            n -= cnt;//一次性将入度为一的点全部删去!!不能一个一个删!
            while (cnt--)
            {
                int temp = myqueue.front();
                myqueue.pop();
                indegree[temp] = 0;
                //更新temp的邻接点:若temp临接点的入度为1,则将其放入queue中。
                for (int i = 0; i < graph[temp].size(); i++)
                {
                    if (indegree[graph[temp][i]] != 0)
                    {
                        indegree[graph[temp][i]]--;
                        if (indegree[graph[temp][i]] == 1)//放在这里做!只判断邻接点。
                            myqueue.push(graph[temp][i]);
                    }
                    
                }
            }
            cnt = myqueue.size();
        }
        vector<int> result;
        while (!myqueue.empty())
        {
            result.push_back(myqueue.front());
            myqueue.pop();
        }
        return result;
    }
    };
    

    相关文章

      网友评论

          本文标题:2020-10-21:最小高度树

          本文链接:https://www.haomeiwen.com/subject/pidpmktx.html