Minimum Height Trees (M)
題目
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 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:
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 * 10^4edges.length == n - 10 <= ai, bi < nai != bi- All the pairs
(ai, bi)are distinct. - The given input is guaranteed to be a tree and there will be no repeated edges.
題意
在給定的無向無環圖中確定一個根結點，使得得到的樹的高度最小，
思路
從最外層的葉結點開始一層一層向里面“剝”，直到只剩最里面的1或2個結點即為答案，具體方法是：根據資訊構建圖，并把所有葉結點加入到佇列中；依次出隊，刪去葉結點，更新葉結點連接的所有結點，并將新生成的葉結點入隊；重復直到只剩1或2個結點，
另一種可行的方法是，先求無向圖的直徑，即葉結點到葉結點的最長路徑，再求這個路徑中間的1或2個結點即為答案，求直徑的具體方法：任選一個結點，用DFS/BFS找到離它最遠的結點A，再從A出發，找到離A最遠的結點B，A-B構成的路徑即為直徑，
代碼實作
Java
class Solution {
public List<Integer> findMinHeightTrees(int n, int[][] edges) {
if (n == 1) {
return new ArrayList<Integer>() {
{
add(0);
}
};
}
Map<Integer, Set<Integer>> g = new HashMap<>();
Queue<Integer> q = new LinkedList<>();
for (int i = 0; i < edges.length; i++) {
int a = edges[i][0], b = edges[i][1];
g.putIfAbsent(a, new HashSet<>());
g.putIfAbsent(b, new HashSet<>());
g.get(a).add(b);
g.get(b).add(a);
}
for (int i = 0; i < n; i++) {
if (g.get(i).size() == 1) {
q.offer(i);
}
}
while (n > 2) {
int size = q.size();
for (int i = 0; i < size; i++) {
int x = q.poll();
for (int y : g.get(x)) {
g.get(y).remove(x);
if (g.get(y).size() == 1) {
q.offer(y);
}
}
}
n -= size;
}
return new ArrayList<>(q);
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/202811.html
標籤：其他