310. Minimum Height Trees

解題思路

照著網路上其他人「一層層剝開 leaf node」的思維去寫。

有空再寫一次。

程式碼

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if(n == 1) return vector<int>(1, 0);
        vector<set<int>> graph(n);
        for(int i=0; i<edges.size(); i++)
        {
            graph[edges[i][0]].insert(edges[i][1]);
            graph[edges[i][1]].insert(edges[i][0]);
        }
        vector<int> leafNode, nextLeafNode;
        for(int i=0; i<n; i++)
        {
            if(graph[i].size() == 1)
                leafNode.push_back(i);
        }

        while(!leafNode.empty())
        {
            for(auto node : leafNode)
            {
                for(auto connect : graph[node])
                {
                    graph[connect].erase(node);
                    if(graph[connect].size() == 1)
                        nextLeafNode.push_back(connect);
                }
            }
            if(nextLeafNode.empty()) break;
            swap(leafNode, nextLeafNode);
            nextLeafNode.clear();
        }
        
        return leafNode;

    }
};