c++ easy to understand solution


  • 0
    J
    public: 
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
            vector<int> res;
            //init the link tabel
            vector<unordered_set<int>> graph(n);
            for(auto edge : edges) {
                graph[edge.first].insert(edge.second);
                graph[edge.second].insert(edge.first);
            }
            //init the degree
            vector<int> degree(n, 0);
            for(int i = 0;i < n;i++) {
                degree[i] = graph[i].size(); 
            }
            for(int i = 0, j, remain = n;i < n && remain > 2;i++) {
                //recore the node index to be deleted and set their degree to -1
                vector<int> del;
                for(int j = 0;j < n;j++) {
                    if(degree[j] == 1) {
                        degree[j] = -1;
                        del.push_back(j);
                        --remain;
                    }
                }
                for(auto index : del)
                    for(auto dec_index: graph[index]) --degree[dec_index];
            }
            for(int i = 0;i < n;i++) {
                if(degree[i] >= 0) res.push_back(i);
            }
            return res;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.