310 - Minimum Height Trees

解法一 - Topological Sort

上面的解法寫得滿清楚的,因為最後的答案就是整個 graph 最核心的那個或兩個 node,所以我們可以利用 topological sort 的概念,一直移除掉只有一條邊連接的 leaf node,實作如下:

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        vector<int> minHeightTrees;
        if (n <= 0) {
            return minHeightTrees;
        }

        if (n == 1) {
            minHeightTrees.push_back(0);
            return minHeightTrees;
        }

        // Build the graph
        unordered_map<int, int> inDegree;
        unordered_map<int, vector<int>> graph;
        for(auto& edge: edges) {
            int n1 = edge[0];
            int n2 = edge[1];

            graph[n1].push_back(n2);
            graph[n2].push_back(n1);
            ++inDegree[n1];
            ++inDegree[n2];
        }

        // Get the leaves
        deque<int> leaves;
        for(auto& p: inDegree) {
            if(p.second == 1) {
                leaves.push_back(p.first);
            }
        }

        // Remove leaves until there are less than two nodes left
        int totalNodes = n;
        while(totalNodes > 2) {
            int leavesSize = leaves.size();
            totalNodes -= leavesSize;

            for (int i = 0; i < leavesSize; i++) {
                int vertex = leaves.front();
                leaves.pop_front();

                for (auto& child : graph[vertex]) {
                    if (--inDegree[child] == 1) {  // if the child has become a leaf
                        leaves.push_back(child);
                    }
                }
            }
        }

        // return the nodes left

        move(begin(leaves), end(leaves), back_inserter(minHeightTrees));
        return minHeightTrees;
    }
};

results matching ""

    No results matching ""