My simple c++ solution


  • 0
    K
     class Solution {
    public:
     vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
        vector<int>res;
        if(edges.size()==0 && n==0)return res;
        if(edges.size()==0 && n!=0)return {0};
        
        vector<int>nums[n];
        for(auto & e : edges){
            nums[e.first].push_back(e.second);
            nums[e.second].push_back(e.first);
        }
        for(int i=0; i < n; i++){
            if(nums[i].size()==1)res.push_back(i);
        }
        
        while(n>2){
            vector<int>leaves;
            n=n - res.size();
            for(auto & node : res)
                for(auto & neighbor : nums[node]){
                    nums[neighbor].erase(find(nums[neighbor].begin(), nums[neighbor].end(),node));
                    if(nums[neighbor].size()==1)leaves.push_back(neighbor);
                }
            res=leaves;
        }
        
        return res;
    }
    } ;

Log in to reply
 

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