624 ms C++ beats 100%


  • 1
    C
    // root of MHT must locate at the middle point of the tree
    // Let's start from leaves, the points with only one edge. Remove all leaves.
    // Then, we will get new leaves, remove all of them again and again like peeling an apple.
    // eventually , we will get only one point (the root of MHT) or one edge (these two points are the roots of MHT)
    
    class Solution {
    public:
    vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
        vector<int> out;
        
        vector<list<int>> e(n);   // adjacency list
        int ne=edges.size();
        if(n==1){   // one node , MHT size==1 rooted at node 0 
            out.push_back(0);
            return out;
        }
        for(int i=0;i<ne;i++){  // build up adjacency list
            e[edges[i].first].push_back(edges[i].second);
            e[edges[i].second].push_back(edges[i].first);
        }
        
        while(ne>1){
            queue<int> ends;
            for(int i=0;i<n;i++){   //push all leaves of pre-peeled tree to queue
                if(e[i].size()==1){
                    ends.push(i);
                }
            }
            if(ne==ends.size()){    // i.e. , after peeling , all edges will be gone so the intersection of these edges is the root
                out.push_back(e[ends.front()].front());
                return out;
            }
            while(!ends.empty()){   // peeling the leaves
            
                    ne--;   // update current edge size
                    int end1=ends.front();  // end point of a leaf
                    int end2=e[end1].front();   // the edged point with this leaf
                    ends.pop(); 
                    e[end1].pop_back(); // update adjacency list
                    for(auto it=e[end2].begin();it!=e[end2].end();it++){
                        if(*it==end1) {
                            e[end2].erase(it);  // update adjacency list
                            break;
                        }
                    }
                
            }
        }
        // after while loop , only one edge left which contains two roots of MHTs
        
        for(int i=0;i<n;i++){
            if(e[i].size()==1){
                out.push_back(i);
                out.push_back(e[i].front());
                break;
            }
        }
        return out;
    }
    

    };


Log in to reply
 

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