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]]
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]
Show Hint
给定一个无向无环图，问以哪个顶点为根形成的有根树的树高是最小的，如果有多个这样的最小高度的有根树，则输出所有这样的根节点。 很有意思的一题，需要把无向无环图转换为有根树。提示问这样的最小高度的有根树最多有多少个，我想了想，应该最多只有两个吧。可以用反证法，假设有3个，则这3个根肯定会形成环，具体原因大家可以在纸上画个图举个例子就知道了。 然后我由题目的样例想到的是，把图转换为有根的最小高度的树，根节点应该是从度数最高的前两个节点中选一个。所以我首先统计了所有节点的度数，然后选两个度数最高的节点，对这两个点DFS求以他们为根时的树高，如果树高相同，说明这两个点都是答案，否则取树高更高的节点作为根节点。 但是很可惜，代码提交之后WA，错误样例是这样的[[0,1],[0,2],[0,3],[2,4],[0,5],[5,6],[6,7],[2,8],[7,9]]。
8 3
\ \
2----0----5----6----7----9
/ /
4 1
在上图中，度数最多的前两个点是0和2，但是转换为有根树的最小高度的树根节点是5。所以我的解法是错误的。
参考网上的题解，好巧妙呀。这种解法类似于剥洋葱，一层一层把叶子节点剥离掉，最后剩下的2个或者1个节点就是最小树高的根节点。这种解法显然是正确的，没剥掉一层，相当于树高减一，一直减，到最后还剩下的节点肯定就是根节点了。比如上图中，第一层剥掉8,3,9,4,1，变成下图
2----0----5----6----8第二层剥掉之后变成下图
0----5----6第三层剥掉之后就只剩下5号节点了，所以以5号节点为根，树的高度最低，只有3，而我的解法算出来的根节点0的树高是4，不是最小的。
5剥洋葱的解法用BFS来实现就非常方便了，BFS天然就是一层循环就是剥掉一层。 代码中，初始时，我们把图转换为类似邻接表的结果，但是每个vector里存的是unordered_set，而不是list，因为剥洋葱的时候，比如第一层时剥掉8号节点时，我们同时需要把2号节点的邻接表中的8号节点删掉，所以用unordered_set.erase就非常方便。后面循环时，没剥一层，我们就检查一下，把当前的叶子节点加入到队列中。当剩余的节点数不超过2个时，剩余的节点就是有根树的根节点。如果剩余两个节点，说明这两个节点的高度是一样的，都是正确答案。 代码如下： [cpp] class Solution { public: vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) { if (n == 1)return{ 0 }; int m = edges.size(); vector<unordered_set<int>> graph(n, unordered_set<int>()); for (int i = 0; i < m; ++i) { graph[edges[i].first].insert(edges[i].second); graph[edges[i].second].insert(edges[i].first); } queue<int> q; for (int i = 0; i < n; ++i) { if (graph[i].size() == 1) q.push(i); } while (n > 2) { int t = q.size(); n -= t; while (t–) { int leaf = q.front(); q.pop(); for (auto par : graph[leaf]) { // only one par graph[par].erase(leaf); if (graph[par].size() == 1)q.push(par); } } } vector<int> ans; while (!q.empty()) { ans.push_back(q.front()); q.pop(); } return ans; } }; [/cpp] 本代码提交AC，用时79MS。]]>