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).

1. 首先，对于顶点数大于2的书，任意两个叶节点一定不是直接相连的。（否则剩下的节点无法和这两个叶节点相连。）
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)$$, 与我们的假设产生矛盾。
3. 如何证明删去所有叶节点，MHT的根不变？以Vi为根的树，其高度为Vi到所有叶节点的最大值。