未分類

Minimum Height Trees

BreadthFirstSearch, Go, Graph, LeetCode

Minimum Height Trees

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:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

1
2
3
4
5
  0
  |
  1
 / \
2   3

return [1]

Example 2:

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

1
2
3
4
5
6
7
0  1  2
 \ | /
   3
   |
   4
   |
   5

return [3, 4]

Note:

(1) 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.”

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

提示 解題應用
Graph 相鄰表製作

Default:

1
2
3
func findMinHeightTrees(n int, edges [][]int) []int {
}

解答思路:

給一無向圖(其實就是樹的形狀，因此不包含相鄰成圈的環)是由n個節點與n-1條邊所組成，找出從哪些點出發到其它節點的最長距離最小，這題的概念與Course Schedule非常相近，都是要先製做相鄰表或關係表再逐步篩選出結果，如果是算出所有節點彼此的距離來找出結果，會花費超過規定內的時間，透過觀查發現出發到其它節點的最長距離最小的那些節點，通常落在整個圖最中間的位置(也就是非葉子節點:相鄰節點數大於1)，而且最中間的節點數最多不超過2個，因此藉由整理出的關係表找出葉子節點再從中移除，最後不斷重覆上述動作直到關係表剩餘的節點數小於等於2就會是我們要的結果。

程式碼解說:

一開始先判斷圖所擁有的邊是否為空，如果是便回傳包含一個0的數字陣列，否則初始化hashmap來作為節點間的關係表(這題以hashmap來存取較為方便)，其中key為節點值而value則是一陣列包含與此節點有關聯的其它節點值，接著再將邊取出並將兩端節點存於關係表中(因為邊是無方向性，所以hashmap上要分別做儲存)，而在不斷篩選掉葉子節點以找出結果之前，要從先前整理好的關係表之中找出葉子節點(相鄰節點數等於1)才能進入下一個步驟

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
if len(edges) == 0 {
	return []int{0}
}
var leaves []int
var newLeaves []int
relations := make(map[int][]int)
for _, edge := range edges {
	relations[edge[0]] = append(relations[edge[0]], edge[1])
	relations[edge[1]] = append(relations[edge[1]], edge[0])
}
for node, rel := range relations {
	if len(rel) == 1 {
		leaves = append(leaves, node)
	}
}

藉由整理關係表找出葉子節點再從中移除，不斷重覆上述動作直到關係表剩餘的節點數小於等於2為止，其中每次都記得要將總節點數減去葉子節點數，以此來得知剩餘節點數，至於將葉子節點從關係表移除，由於葉子節點只會有一個關聯的節點，因此在hashmap取值時只要取陣列的第一個值也就是index為0的位置，接著反過來在該關聯的節點移除對應到陣列的葉子節點值，這邊是再用一迴圈逐一遍歷直到找出葉子節點的index位置再移除(重新組合陣列以跳過葉子節點值)，而如果該關聯的節點對應到的陣列在移除葉子節點後長度變為1，此時該節點就變為下一組新的葉子節點之一，最後如果剩餘的節點數小於等於2，便向上回傳剩餘的(葉子)節點值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
for n > 2 {
	n -= len(leaves)
	newLeaves = make([]int, 0)
	for _, leaf := range leaves {
		node := relations[leaf][0]
		for i, v := range relations[node] {
			if v == leaf {
				relations[node] = append(relations[node][:i], relations[node][i+1:]...)
				break
			}
		}
		if len(relations[node]) == 1 {
			newLeaves = append(newLeaves, node)
		}
		leaves = newLeaves
	}
}
return leaves

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
func findMinHeightTrees(n int, edges [][]int) []int {
	if len(edges) == 0 {
		return []int{0}
	}
	var leaves []int
	var newLeaves []int
	relations := make(map[int][]int)
	for _, edge := range edges {
		relations[edge[0]] = append(relations[edge[0]], edge[1])
		relations[edge[1]] = append(relations[edge[1]], edge[0])
	}
	for node, rel := range relations {
		if len(rel) == 1 {
			leaves = append(leaves, node)
		}
	}
	for n > 2 {
		n -= len(leaves)
		newLeaves = make([]int, 0)
		for _, leaf := range leaves {
			node := relations[leaf][0]
			for i, v := range relations[node] {
				if v == leaf {
					relations[node] = append(relations[node][:i], relations[node][i+1:]...)
					break
				}
			}
			if len(relations[node]) == 1 {
				newLeaves = append(newLeaves, node)
			}
			leaves = newLeaves
		}
	}
	return leaves
}

總結:

給一無向圖(其實就是樹的形狀，因此不包含相鄰成圈的環)是由n個節點與n-1條邊所組成，找出從哪些點出發到其它節點的最長距離最小，先製做相鄰表或關係表再逐步篩選出結果，如果是算出所有節點彼此的距離來找出結果，會花費超過規定內的時間，透過觀查發現出發到其它節點的最長距離最小的那些節點，通常落在整個圖最中間的位置(也就是非葉子節點:相鄰節點數大於1)，而且最中間的節點數最多不超過2個，因此藉由整理出的關係表找出葉子節點再從中移除，最後不斷重覆上述動作直到關係表剩餘的節點數小於等於2就會是我們要的結果。

分享到