[recommend for beginners]clean C++ implementation with detailed explanation


  • 7

    My implementation just follows the idea that the-path-method inspired from

    http://algobox.org/minimum-height-trees/

    Just like topological sorting, we delete the in-degree-1-node level by level.

    Just we can ensure that the path of the longest length will be left.

    So the last 1 or last 2 node is the solution

    class Solution {
        public:
            vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
                vector<int> result;
                if(n==1) { result.push_back(0); return result; }
                vector<unordered_set<int>> graph(n, unordered_set<int>());
                for(int i=0; i<edges.size(); i++){
                    graph[edges[i].first].insert(edges[i].second);
                    graph[edges[i].second].insert(edges[i].first);
                }
                vector<int> degree(n, 0);
                for(int i=0; i<n; i++){
                    degree[i]=graph[i].size();
                    cout<<i<<":"<<degree[i]<<endl;
                }
                int count=n;
                while(count>2){
                    vector<int> record;
                    for(int i=0; i<n; i++){
                        if(degree[i]==1) {
                            count--;
                            degree[i]=-1;
                            record.push_back(i);
                        }
                    }
                    for(int i=0; i<record.size(); i++){
                        for(auto it : graph[record[i]])  degree[it]--;
                    }
                }
                for(int i=0; i<n; i++){
                    if(degree[i]==1 || degree[i]==0)  result.push_back(i);
                }
                return result;
            }
        };
    

  • 0
    2
    class Solution {
    public:
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
            vector<int> in_degree(n, 0);
            unordered_map<int, vector<int>> graph;
            for(auto edge : edges) {
                in_degree[edge.first]++;
                in_degree[edge.second]++;
                graph[edge.first].push_back(edge.second);
                graph[edge.second].push_back(edge.first);
            }
            
            /*** store the in-degree=1 node **/
            int count = n;
            int level = 0;
            /** bug **/
            
            while(count > 2) {
                level++;
                vector<int> can_set;
                for(int i = 0; i < n; i++) {
                    if(in_degree[i] == 1) {
                        in_degree[i] = -1;
                        can_set.push_back(i);
                        count--;
                    }
                }
                for(auto it : can_set) {
                    for(auto neighbor : graph[it]) {
                        in_degree[neighbor]--;
                    }
                }
            }
            
            vector<int> result;
            for(int i=0; i<n; i++) {
                if(in_degree[i] == 0 || in_degree[i] == 1) {
                    result.push_back(i);
                }
            }
            return result;
        }
    };

Log in to reply
 

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