310 Minimum Height Trees
For an 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]
Hint: How many MHTs can a graph have at most
- Note:
- 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.”
- The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.
Solution
逐层删去叶结点
class Solution {
public:
vector<int> findMinHeightTrees(int n, vector<pair<int, int>>& edges) {
unordered_map<int, unordered_set<int>> graph;
for ( auto edge : edges ) {
graph[edge.first].insert(edge.second);
graph[edge.second].insert(edge.first);
}
vector<int> depth(n, 0);
for ( int i = 0; i <= n-1; i++ ) depth[i] = graph[i].size();
for ( int remain = n; remain >= 3;) {
vector<int> del;
for ( int i = 0; i <= n-1; i++ ) {
if ( depth[i] != 1 ) continue;
depth[i] -= 1;
del.push_back(i);
remain -= 1;
}
for ( auto idel : del ) {
for ( auto end : graph[idel] ) {
depth[end] -= 1;
graph[end].erase(graph[end].find(idel));
}
graph.erase(graph.find(idel));
}
}
vector<int> res;
for ( int i = 0; i <= n-1; i++ ) {
if ( graph.find(i) != graph.end() ) res.push_back(i);
}
return res;
}
};
Notes
We should fully utilize the property of a tree-like undirected graph.
https://en.wikipedia.org/wiki/Tree_(graph_theory)
A tree is an undirected graph G that satisfies any of the following equivalent conditions:
- A tree with n vertices has n − 1 edges.
- Any tree with at least two vertices has at least two leaf vertices.
- In any tree with more than three vertices, the leaf vertices cannot be the root of a minimum-height tree (MHT).
- 首先,对于顶点数大于2的书,任意两个叶节点一定不是直接相连的。(否则剩下的节点无法和这两个叶节点相连。)
- 下面试图证明,对于顶点数大于2的树,叶节点一定不是MHT的根节点。用反证法, 假设叶节点$$V_1$$是MHT的根节点,且树高为$$h$$。这意味着$$V_1$$到其他所有结点 $$V_2, V_3 ... V_n$$ 的距离都不大于$$h$$。我们考虑V1唯一的邻居,设为$$V_x$$。由于树的性质,我们知道所有联通$$V_1$$和$$V_i$$的路径必定经过Vx。则从$$V_x$$到所有其他结点的距离都不大于$$(h-1)$$。所以以$$V_x$$为根节点的树的树高为$$(h-1)$$, 与我们的假设产生矛盾。
- 如何证明删去所有叶节点,MHT的根不变?以Vi为根的树,其高度为Vi到所有叶节点的最大值。