Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - C++ - 310. Minimum Height Trees

---

題目：


方法：

這題的核心不是從每個點去算高度(那會Timeout)，而是不斷移除葉子(degree = 1)，直到剩下1~2個節點，這些剩下的點就是答案(樹的中心)

解答：

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

        vector<vector<int>> graph(n);
        vector<int> degree(n, 0);

        for (auto& e : edges) {
            int u = e[0];
            int v = e[1];

            graph[u].push_back(v);
            graph[v].push_back(u);
            degree[u] += 1;
            degree[v] += 1;
        }

        queue<int> q;
        for (int i = 0; i < n; ++i) {
            if (degree[i] == 1) {
                q.push(i);
            }
        }

        int remaining = n;
        while (remaining > 2) {
            int size = q.size();
            remaining -= size;

            for (int i = 0; i < size; ++i) {
                int leaf = q.front(); q.pop();

                for (int n : graph[leaf]) {
                    degree[n] -= 1;
                    if (degree[n] == 1) {
                        q.push(n);
                    }
                }
            }
        }

        vector<int> ans;
        while (!q.empty()) {
            ans.push_back(q.front());
            q.pop();
        }

        return ans;
    }
};