[LeetCode] 310. Minimum Height Trees

轉自LeetCode

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges(each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1 :

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

        0
        |
        1
       / \
      2   3 

Output: [1]

Example 2 :

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

     0  1  2
      \ | /
        3
        |
        4
        |
        5 

Output: [3, 4]

Note:

• According to the definition of tree on Wikipedia: “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.”
• The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

<Solution>

想法如下

• 這題的思路和 topological sorting 有點類似。先從一個數列來看，找到一個位置，離兩端的距離有最短值，那個位置就是在中間的位置 (如果數列長度是偶數的話，那就是中間那兩個位置)，所以這題要找的，就是在最長路徑上的中間位置

• 在數列上，可以用兩個指標分別兩端出發，當兩個指標指在同一個位置，或是相隔 1，那麼就是要找的答案

• 這題的 input 是一個無向圖，利用 topological sorting 的想法來看，可以先找到最邊緣，也就是只和一個節點有 edge 的節點，來當作起端，就像是在數列上，是從兩端開始，在無向圖上，就找到最邊緣的 leaf node，這樣才是在最長路徑上找

• 從 leaf node 出發，然後把它和它相連 node 之間的 edge，從無向圖中刪除，看看是否有找到新的 leaf node，就這樣一層一層向中間邁進

• 上面這個步驟，終止的條件在於 n <= 2。如同前面提到的，這題的答案會是中間那個位置(長度是奇數時)，或是中間那兩個位置(長度是偶數時)，所以每次歷遍 leaf node 的時候，都將 n 減掉當下 leaf node 的個數

code 如下

Java(參考解法)

	class Solution {
	public List<Integer> findMinHeightTrees(int n, int[][] edges) {
	if(n == 1) {
	return Collections.singletonList(0);
	}
	List<Set<Integer>> adjList = new ArrayList<>();
	for(int i = 0; i < n; i++) {
	adjList.add(new HashSet<Integer>());
	}
	for(int[] edge : edges) {
	adjList.get(edge[0]).add(edge[1]);
	adjList.get(edge[1]).add(edge[0]);
	}
	List<Integer> leaves = new ArrayList<>();
	for(int i = 0; i < n; i++) {
	if(adjList.get(i).size() == 1) {
	leaves.add(i);
	}
	}
	int num;
	while(n > 2) {
	n -= leaves.size();
	List<Integer> newLeaves = new ArrayList<>();
	for(int i : leaves) {
	num = adjList.get(i).iterator().next();
	adjList.get(num).remove(i);
	if(adjList.get(num).size() == 1) {
	newLeaves.add(num);
	}
	}
	leaves = newLeaves;
	}
	return leaves;
	}
	}

view raw findMinHeightTrees.java hosted with ❤ by GitHub

Kotlin

	class Solution {
	fun findMinHeightTrees(n: Int, edges: Array<IntArray>): List<Int> {
	return if(n == 1) {
	listOf(0)
	} else {
	val nodes = arrayListOf<MutableSet<Int>>()
	for(i in 1..n) {
	nodes.add(mutableSetOf())
	}
	for(e in edges) {
	nodes.get(e[0]).add(e[1])
	nodes.get(e[1]).add(e[0])
	}
	var leaves = arrayListOf<Int>()
	for(i in nodes.indices) {
	if(nodes.get(i).size == 1) {
	leaves.add(i)
	}
	}
	var count = n
	var label: Int
	while(count > 2) {
	count -= leaves.size
	val newLeaves = arrayListOf<Int>()
	for(i in leaves) {
	label = nodes.get(i).first() // leave only have one connected node
	nodes.get(label).remove(i)
	if(nodes.get(label).size == 1) {
	newLeaves.add(label)
	}
	}
	leaves = newLeaves
	}
	leaves
	}
	}
	}

view raw minimum_height_trees.kt hosted with ❤ by GitHub