LeetCode 310 Minimum Height Trees

LeetCode 310 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]]

        0
        |
        1
       / \
      2   3

return [1]

Example 2:

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

     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.

题目大意：

对于一棵无向树，我们可以选择它的任意节点作为根。得到的结果就是有根树。在所有可能的有根树中，高度最小的称为最小高度树（MHT）。
给定一个无向图，编写函数找出所有的最小高度树，并返回其根标号的列表。

解题思路：

此题本质上求最长路径上的中间1-2个节点。由于根节点不确定，从叶节点出发，层层剥离，这就是拓扑排序(inDegree数组)。而且需要知道最后一层的1-2个节点，所以考虑用按层遍历BFS（两数组）。见KB。

注意事项：

1. 由于最后一层可能是1-2个节点，所以要用一个变量res把最后一层记录下来, res = list(queue)在开始和循环中。
2. 还有一点要注意的是这是无向图，所以入度=1而不是0时候即入队列。
3. 单一节点(没有边)返回空列表

Python代码：

def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
	if not edges:
		return [0] # remember
	graph = collections.defaultdict(list)
	in_degree = [0] * n
	for li in edges:
		graph[li[0]].append(li[1])
		graph[li[1]].append(li[0])
		in_degree[li[0]] += 1
		in_degree[li[1]] += 1
	queue = collections.deque([i for i in range(len(in_degree)) if in_degree[i] == 1])
	res = list(queue) # remember
	while queue:
		for _ in range(len(queue)):
			node = queue.popleft()
			for neighbor in graph[node]:
				in_degree[neighbor] -= 1
				if in_degree[neighbor] == 1:
					queue.append(neighbor)
		if queue: # remember
			res = list(queue)
	return res

注意事项：

1. 由于最后一层可能是1-2个节点，所以要用一个变量把最后一层记录下来。
2. 还有一点要注意的是这是无向图，所以入度=1而不是0时候即入队列。

Topological:

1. 根据边统计每个节点的入度数记入in[i]
2. 找出度数为0的节点加入到Queue
3. 取出队首节点，把此节点邻接的节点度数减1，如果度数为0，加入到队列，循环直到队列为空

Java代码：

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
	if(n==1 && edges.length==0){
		return new ArrayList<Integer>(Arrays.asList(new Integer[]{0}));
	}
	ArrayList<ArrayList<Integer>> graph = new ArrayList<ArrayList<Integer>>();
	int num = n;
	for(int i=0;i<n;i++)
		graph.add(new ArrayList<Integer>());
	int[] inDegree = new int[n];
	//populate inDegree & convert to graph
	for(int i=0;i<edges.length;i++){
		inDegree[edges[i][0]]++;
		inDegree[edges[i][1]]++;
		graph.get(edges[i][1]).add(edges[i][0]);
		graph.get(edges[i][0]).add(edges[i][1]);
	}
	Queue<Integer> q = new LinkedList<Integer>();
	Queue<Integer> q2 = new LinkedList<Integer>();

	for(int i=0;i<inDegree.length;i++){
		if(inDegree[i]==1)
			q.offer(i);
	}
	Queue<Integer> lastLayerQ = new LinkedList<Integer>(q);
	while(!q.isEmpty()){
		Integer v = q.poll();
		for(int neighbor : graph.get(v)){
			if(--inDegree[neighbor]==1)
				q2.offer(neighbor);
		}
		if(q.isEmpty() && !q2.isEmpty()){
			q = q2;
			q2 = new LinkedList<Integer>();
			lastLayerQ = new LinkedList<Integer>(q);
		}
			
	}

	return (List)lastLayerQ;
}

算法分析：

时间复杂度为O(n)，w为树的所有层里面的最大长度，空间复杂度O(w)。