310 Minimum Height Trees 最小高度樹

Description:
A tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.

Given a tree of n nodes labelled from 0 to n - 1, and an array of n - 1 edges where edges[i] = [ai, bi] indicates that there is an undirected edge between the two nodes ai and bi in the tree, you can choose any node of the tree as the root. When you select a node x as the root, the result tree has height h. Among all possible rooted trees, those with minimum height (i.e. min(h)) are called minimum height trees (MHTs).

Return a list of all MHTs' root labels. You can return the answer in any order.

The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

Example:

Example 1:

Trees 1

Input: n = 4, edges = [[1,0],[1,2],[1,3]]
Output: [1]
Explanation: As shown, the height of the tree is 1 when the root is the node with label 1 which is the only MHT.

Example 2:

Trees 2

Input: n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
Output: [3,4]

Example 3:

Input: n = 1, edges = []
Output: [0]

Example 4:

Input: n = 2, edges = [[0,1]]
Output: [0,1]

Constraints:

1 <= n <= 2 * 104
edges.length == n - 1
0 <= ai, bi < n
ai != bi
All the pairs (ai, bi) are distinct.
The given input is guaranteed to be a tree and there will be no repeated edges.

題目描述:
對(duì)于一個(gè)具有樹特征的無(wú)向圖，我們可選擇任何一個(gè)節(jié)點(diǎn)作為根。圖因此可以成為樹，在所有可能的樹中，具有最小高度的樹被稱為最小高度樹。給出這樣的一個(gè)圖，寫出一個(gè)函數(shù)找到所有的最小高度樹并返回他們的根節(jié)點(diǎn)。

格式

該圖包含 n 個(gè)節(jié)點(diǎn)，標(biāo)記為 0 到 n - 1。給定數(shù)字 n 和一個(gè)無(wú)向邊 edges 列表（每一個(gè)邊都是一對(duì)標(biāo)簽）。

你可以假設(shè)沒(méi)有重復(fù)的邊會(huì)出現(xiàn)在 edges 中。由于所有的邊都是無(wú)向邊， [0, 1]和 [1, 0] 是相同的，因此不會(huì)同時(shí)出現(xiàn)在 edges 里。

示例 :

示例 1:

輸入: n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3 

輸出: [1]

示例 2:

輸入: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5 

輸出: [3, 4]

說(shuō)明:
根據(jù)樹的定義，樹是一個(gè)無(wú)向圖，其中任何兩個(gè)頂點(diǎn)只通過(guò)一條路徑連接。 換句話說(shuō)，一個(gè)任何沒(méi)有簡(jiǎn)單環(huán)路的連通圖都是一棵樹。
樹的高度是指根節(jié)點(diǎn)和葉子節(jié)點(diǎn)之間最長(zhǎng)向下路徑上邊的數(shù)量。

思路:

拓?fù)渑判?br> 每一輪將度為 1的結(jié)點(diǎn)刪除直到剩下最后一個(gè)或兩個(gè)結(jié)點(diǎn)
時(shí)間復(fù)雜度O(n ^ 2), 空間復(fù)雜度O(n)

代碼:
C++:

class Solution 
{
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) 
    {
        vector<int> result;
        queue<int> q;
        vector<unordered_set<int>> graph(n);
        for (auto &edge : edges)
        {
            graph[edge[0]].insert(edge[1]);
            graph[edge[1]].insert(edge[0]);
        }
        for (int i = 0; i < n; i++) if (graph[i].size() == 1) q.push(i);
        while (n > 2)
        {
            int size = q.size();
            n -= size;
            while (size-- > 0)
            {
                int v = q.front();
                q.pop();
                for (auto &next : graph[v])
                {
                    graph[next].erase(v);
                    if (graph[next].size() == 1) q.push(next);
                }
            }
        }
        if (q.empty()) result.emplace_back(0);
        while (!q.empty())
        {
            result.emplace_back(q.front());
            q.pop();
        }
        return result;
    }
};

Java:

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> result = new ArrayList<>(), queue = new ArrayList<>();
        boolean graph[][] = new boolean[n][n], visited[] = new boolean[n];
        int count = n, inDegree[] = new int[n];
        for (int[] edge : edges) {
            graph[edge[0]][edge[1]] = true;
            graph[edge[1]][edge[0]] = true;
            ++inDegree[edge[0]];
            ++inDegree[edge[1]];
        }
        while (count > 2) {
            findOuter(queue, inDegree);
            while (!queue.isEmpty()) {
                int v = queue.remove(0);
                --inDegree[v];
                visited[v] = true;
                --count;
                for (int i = 0; i < n; i++) {
                    if (graph[v][i]) {
                        graph[v][i] = false;
                        graph[i][v] = false;
                        --inDegree[i];
                    }
                }
            }
        }
        for (int i = 0; i < n; i++) if (!visited[i]) result.add(i);
        return result;
    }
    
    private void findOuter(List<Integer> queue, int[] inDegree) {
        for (int i = 0; i < inDegree.length; i++) if (inDegree[i] == 1) queue.add(i);
    }
}

Python:

class Solution:
    def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
        if n == 2:
            return [0, 1]
        if n == 1:
            return [0]
        graph, in_degree, q, visited, count = defaultdict(list), [0] * n, deque(), [False] * n, n
        for edge in edges:
            graph[edge[0]].append(edge[1])
            graph[edge[1]].append(edge[0])
            in_degree[edge[0]] += 1
            in_degree[edge[1]] += 1
        for i in range(n):
            if in_degree[i] == 1:
                q.append(i)
        while q:
            size = len(q)
            n -= size
            for _ in range(size):
                v = q.popleft()
                w = graph[v].pop()
                graph[w].remove(v)
                in_degree[v] -= 1
                in_degree[w] -= 1 
                if in_degree[w] == 1:
                    q.append(w)
            if n == 1:
                return [q.popleft()]
            if n == 2:
                return [q.popleft(), q.popleft()]