題目網址：https://leetcode.cn/problems/minimum-height-trees/

題意：給一數字 n 和 n - 1 條無向邊的 edges list, 代表一包含 n 個 node 編號從 0 到 n - 1 的 tree。

可選擇 tree 中任意 node 作為 root。在所有可能的 tree 中, 具有最小高度的 tree 被稱為最小高度樹。

找到所有最小高度樹的 root 並按任意順序返回。

Solution 1：

想法：利用 Topological Sort + BFS, 我們發現若希望高度越小, 則 root 應選 degree 越大的。

下圖中, 紅圈以外的是 leaf, 若將這些點作為 root, 其樹高不可能為最小的, 原因如下:

  • 若將 leaf 作為 root, 其樹高的路徑必「走進」紅圈, 再「走出」紅圈

  • 若將 non-leaf 為 root, 其樹高的路徑只需「走出」紅圈

➔ 故可透過「剝洋蔥」的方式, 一層一層剝掉 degree = 1 的 node, 直到剩下 ≤ 兩個 node。

思考: 為何不是三個 node 就停呢? 因為三個 node 可以繼續剝下去

特殊情況：當 tree 只有一個 node 時, 則答案即為該 node 本身

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

        vector<unordered_set<int>> adj(n); // adjacency list
        for (const auto& e : edges) {
            adj[e[0]].emplace(e[1]);
            adj[e[1]].emplace(e[0]);
        }

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

        // bfs
        while (n > 2) {
            const int k = q.size();
            n -= k;

            for (int i = 0; i < k; ++i) {
                const auto cur = q.front();
                q.pop();

                // 讓 adjacent node 的 degree - 1
                for (const auto& v : adj[cur]) {
                    adj[v].erase(cur);
                    if (adj[v].size() == 1) {
                        q.emplace(v);
                    }
                }
            }
        }

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

        return res;
    }
};

  • time：$O(n)$ ➔ $O(n+(n-1))$, 其實就是對圖進行 BFS 所需之時間複雜度 $O(V+E)$

    • $O(V)$：n 個 node
    • $O(E)$：n - 1 條 edge, 因為 tree 是 acyclic

  • space：$O(n)$ ➔ $O(n+(n-1))$, 因為 adj 為 $O(V + E)$, V 是因為要記錄所有點, E 是因為會記錄所有邊

Solution 2：

想法：利用 DFS, tree 中最長 path 的兩端點皆必為 leaf, 否則 path 可繼續拓展, 我們的目標就是找出最長 path 之中點

  • 先隨機選取一個 node（可能不為 leaf）, 並對其進行 dfs 取得離它最遠的點 n1（第一個 leaf）
  • 對 n1 進行 dfs 取得離它最遠的點 n2（第二個 leaf）
  • 此時, n1 -> n2 為 tree 中最長的 path, 其 path 之中點即為答案
    • 若 path 長度為奇數, 則取 {path[len / 2]}
    • 若 path 長度為偶數, 則取 {path[(len / 2) - 1], path[len / 2]}

e.g. 下圖中

  • 首先選取 1 並做 dfs 取得 n1 = 6

  • 再對 n1 做 dfs 得 n2 = 7。 n1 -> n2 之 path 長度為 5（6 -> 4 -> 1 -> 5 -> 7）

  • 取 path 中點 1 會得到最小高度樹

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

        vector<unordered_set<int>> adj(n); // adjacency list
        for (const auto& e : edges) {
            adj[e[0]].emplace(e[1]);
            adj[e[1]].emplace(e[0]);
        }

        vector<int> parent(n, -1);
        int n1 = findFarestNode(0, parent, adj, n);
        int n2 = findFarestNode(n1, parent, adj, n);

        vector<int> path;
        parent[n1] = -1; // 將 n1 的 parent 設為 -1

        while (n2 != -1) { // 從 n2 往 n1 走, 並把 node 加到 path 中
            path.emplace_back(n2);
            n2 = parent[n2];
        }

        const int k = path.size();
        if (k % 2) {
            return {path[k / 2]};
        }

        return {path[(k / 2) - 1], path[k / 2]};
    }

private:
    int findFarestNode(int cur, vector<int>& parent, const vector<unordered_set<int>>& adj, int& n){
        vector<int> dis(n, -1);
        dis[cur] = 0;
        dfs(cur, dis, adj, parent);

        int node = 0; // farest node
        for (int i = 1; i < n; ++i) {
            node = (dis[i] > dis[node]) ? i : node;
        }

        return node;
    }

    void dfs(int cur, vector<int>& dis, const vector<unordered_set<int>>& adj, vector<int>& parent){
        for (const auto& v : adj[cur]) {
            if (dis[v] < 0) {
                dis[v] = dis[cur] + 1;
                parent[v] = cur;
                dfs(v, dis, adj, parent);
            }
        }
    }
};
  • time：$O(n)$ ➔ $O(n+(n-1))$, 其實就是對圖進行 DFS 所需之時間複雜度 $O(V+E)$
    • $O(V)$：n 個 node
    • $O(E)$：n - 1 條 edge, 因為 tree 是 acyclic
  • space：$O(n)$ ➔ $O(n+(n-1))$, 因為 adj 為 $O(V + E)$, V 是因為要記錄所有點, E 是因為會記錄所有邊