LeetCode Minimum Height Trees

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

    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.


    给定一个无向无环图,问以哪个顶点为根形成的有根树的树高是最小的,如果有多个这样的最小高度的有根树,则输出所有这样的根节点。

    很有意思的一题,需要把无向无环图转换为有根树。提示问这样的最小高度的有根树最多有多少个,我想了想,应该最多只有两个吧。可以用反证法,假设有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个时,剩余的节点就是有根树的根节点。如果剩余两个节点,说明这两个节点的高度是一样的,都是正确答案。

    代码如下:

    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;
    	}
    };
    

    本代码提交AC,用时79MS。

    Leave a Reply

    Your email address will not be published. Required fields are marked *