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

return [1]

Example 2:

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

return [3, 4]

Show Hint How many MHTs can a graph have at most? 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.

s思路: 1. 提示很重要。不看的时候，只想到了简单粗暴的方法。能不能先遍历，找到最长的path的长度，如果长度为奇数，则只有一个root，即：path的中点是minimum height tree的root；如果长度是偶数，则有两个,在path中间。 2. 如何快速找到最长的path呢？需要每个位置为root分别遍历吗？如果这样的话，复杂度就是o(V(V+E))。但，潜意识感觉这样有很多重复运算。 3. 刚想了一个方法：不用全部遍历，而是先从任意节点开始，做bfs,看最后一层节点的个数，如果只有一个，表示从这个节点就可以找到最长的path;如果大于一个，那么从其中任一节点都可以得到最长path， 然后再遍历一次，给每个节点标记层次数，最后找出符合要求的层数数中的节点输出即可！这样一来，复杂度就是o(v+e). 4. 要做两次遍历，还是不方便，不简洁。看了以前的答案，还是用的经典的bfs检查cycle的方法，记录degree，由于这里是undirected graph,所以没有入度和出度一说，直接统计每个节点有几个neighbor。由于已知是没有cycle,那么统计了degree的好处是可以从图的边缘入手去找root，把所有的degree=1的点放在queue,然后每次从queue取出节点，把这些节点的邻居节点的degree减一，如果减一后也碰巧等于１，说明去掉这条边，其邻居也成了新的边界。如此这般，知道n==2或小于2，此时queue里面剩下的就是中心了。 5. 为什么bfs+统计degree可以办到这件事呢？也就是说图的问题很多都可以用bfs+统计degree的放法是为什么？原因，我觉得应该是这种方法可以从结构上结构图，剖析图，把图的性质给显露出来。比如这道题，求最小height，但height又是最长路径，所以从结构入手，就从leaf入手，而degree=1的节点就是leaf,从leaf入手一步一步反推就可以到root 6. 换个思路，我自己想的思路是从root开始做bfs，发现至少都要做两次bfs，有重复之嫌；从相反角度考虑，从leaf入手，就简单一些，而从leaf入手对bfs来说恰好有这个方法：统计入度或度。换个角度看问题而已，无所谓谁好谁坏，提供多角度的原因只是试图还原事物的本来面部，或者试图从多个角度来看事物。如果只看到一个角度，那一定是人偏执的认为只有一个角度，或这某个角度比其他角度好！