LeetCode-310 Minimum Height Trees

题目描述

For an 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.

题目大意

给出一组点之间的关系，要求从所给的点中找出一个点作为根节点，使得形成的树的高度最低。

示例

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

        0
        |
        1
       / 
      2   3 

Output: [1]

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

     0  1  2
       | /
        3
        |
        4
        |
        5 

Output: [3, 4]

解题思路

保存所有结点的度，每次找到叶节点并将其删除，此时会有新的叶节点出现，再进行遍历删除叶节点。。。最后剩下的一个或两个结点就是可能的根节点。

复杂度分析

时间复杂度：O(V + E)

空间复杂度：O(V + E)

代码

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<unordered_set<int> > node(n);
        // 保存各节点的邻结点
        for(int i = 0; i < edges.size(); ++i) {
            node[edges[i][0]].insert(edges[i][1]);
            node[edges[i][1]].insert(edges[i][0]);
        }
        // 保存各结点的度
        vector<int> degree(n, 0);
        for(int i = 0; i < n; ++i)
            degree[i] = node[i].size();
        // 遍历各个结点
        for(int i = 0, remain = n; i < n && remain > 2; ++i) {
            vector<int> del;
            // 查找叶节点
            for(int j = 0; j < n; ++j) {
                if(degree[j] == 1) {
                    --remain;
                    del.push_back(j);
                    degree[j] = -1;
                }
            }
            // 删除叶节点
            for(auto k : del) {
                for(auto neigh : node[k])
                    degree[neigh]--;
            }
        }
        // 剩余的结点为可能的根节点
        vector<int> res;
        for(int i = 0; i < n; ++i) {
            if(degree[i] >= 0)
                res.push_back(i);
        }
        return res;
    }
};