310. Minimum Height Trees

Description

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

graph

return [1]

Example 2:

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

graph

return [3, 4]

Note:

(1) According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactlyone 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.

Credits:
Special thanks to @dietpepsi for adding this problem and creating all test cases.

Solution

Topological sort

First let’s review some statement for tree in graph theory:

A tree is an undirected graph in which any two vertices are
connected by exactly one path.
Any connected graph who has n nodes with n-1 edges is a tree.
The degree of a vertex of a graph is the number of
edges incident to the vertex.
A leaf is a vertex of degree 1. An internal vertex is a vertex of degree at least 2.（也就是说叶子节点的度是1）
A path graph is a tree with two or more vertices that is not
branched at all.
A tree is called a rooted tree if one vertex has been designated the root.
The height of a rooted tree is the number of edges on the longest downward path between root and a leaf.

根据以上特性，可以采用类似Topologic sort的方式解决。

考虑如果这是一个最简单的path tree，想要找到root，只需用两个pointer分别指向path的两端，然后以同样的速度往中间移动，pointer相遇的位置即为root；

将思路扩展到tree，在每个leaf节点都放置一个pointer，然后将所有pointer以同样的速度向中心移动（农村包围城市），任意两个pointer相遇则停止，就这样移动到最后两个pointer相遇，这个位置即为所求。

考虑如何实现。首先构造一个graph，然后将最外层的leaf节点删除掉（连同连接它的edge），然后将新的leaf节点及edge删除掉，重复执行直到剩下一个或两个节点为止。最终剩下的节点即为所求。

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) {   // no edge
            return Collections.singletonList(0);
        }
        
        Set<Integer>[] graph = new HashSet[n];
        for (int i = 0; i < n; ++i) {
            graph[i] = new HashSet<>();
        }
        
        for (int[] edge : edges) {
            graph[edge[0]].add(edge[1]);
            graph[edge[1]].add(edge[0]);
        }
        
        List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; ++i) {
            if (graph[i].size() == 1) {     // it's a leaf
                leaves.add(i);
            }
        }
        
        while (n > 2) {
            n -= leaves.size();
            List<Integer> newLeaves = new ArrayList<Integer>();
            
            for (int leaf : leaves) {
                for (int parent : graph[leaf]) {
                    graph[parent].remove(leaf);     // remove edge
                    if (graph[parent].size() == 1) {    // becomes leaf
                        newLeaves.add(parent);
                    }
                }
            }
            
            leaves = newLeaves;
        }
        
        return leaves;
    }
}