Share some thoughts implementation in C++


  • 0
    D
    class Solution {
    public:
        vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
            vector<vector<int>> adjList(n);
            vector<int> leafNodes;
            map<int, int> count;
            if(n==0) return leafNodes;
            if(n==1){ leafNodes.push_back(0); return leafNodes; }
            int totEdges=0;
            for(int i=0;i<edges.size();i++) {
                adjList[edges[i].first].push_back(edges[i].second);
                adjList[edges[i].second].push_back(edges[i].first);
                count[edges[i].first]++;
                count[edges[i].second]++;
                totEdges+=2;
            }
            for(auto i:count) {
                if(i.second == 1) {
                    leafNodes.push_back(i.first); //get initial set of leafNodes;
                }
            }
            while(totEdges>2) { //When total edges are less than equal to 2 number of elements is 1or2
                vector<int> newLeafNodes;
                while(!leafNodes.empty()) {
                    int leafNode = leafNodes.front();
                    leafNodes.erase(leafNodes.begin());
                    int rmEdge = adjList[leafNode].front();
                    if(--count[rmEdge] == 1) {
                        newLeafNodes.push_back(rmEdge); //Add new leaf nodes which will be traversed at next iteration
                    } 
                    adjList[rmEdge].erase(remove(adjList[rmEdge].begin(),adjList[rmEdge].end(),leafNode), adjList[rmEdge].end()); //Keep removing edges when they are done traversing
                    totEdges-=2;
                }
                leafNodes=newLeafNodes;
            }
            return leafNodes;
        }
    };
    

Log in to reply
 

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