[Leetcode]310. Minimum Height Trees

Question

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]

Solution

First of all, we can think a simple situation. What’s the MHT for a one path tree? The answer is pretty straight forward, the middle 1 or 2 points, depends on even or odd nodes the tree has, is the MHTs.

Now we can expand to the general situation. There are 2 ways to solves this problem.

1. Randomly select a node x as the root, do a dfs/bfs to find the node y that has the longest distance from x. Then y must be one of the endpoints on some longest path. Let y the new root, and do another dfs/bfs. Find the node z that has the longest distance from y.

2. Delete the leaves from tree repeatedly. Use a list of hash set to store the relation of graph. Delete 0 in-degree nodes. the last one or two nodes is the middle point.

   public class Solution {
       public List<Integer> findMinHeightTrees(int n, int[][] edges) {
            if(n <= 1) {
               return Collections.singletonList(0);
           }
           
           List<Set<Integer>> graph = new ArrayList<Set<Integer>>();
          
           for(int i = 0 ; i < n ; i++){
               graph.add( new HashSet<Integer>() );
           }
           for(int[] edge : edges){
               graph.get(edge[1]).add(edge[0]);
               graph.get(edge[0]).add(edge[1]);
           }
           
           List<Integer> leaves = new ArrayList<Integer>();
           for(int i = 0 ; i < n ; i++){
               if( graph.get(i).size() == 1 ){
                   leaves.add(i);
               }
           }
           
           while( n > 2 ){
               n -= leaves.size();
               List<Integer> newLeaves = new ArrayList<Integer>();
               for(int leave : leaves ){
                   for(int newLeaf : graph.get(leave) ){
                       graph.get(leave).remove(newLeaf);
                       graph.get(newLeaf).remove(leave);
                       if(graph.get(newLeaf).size() == 1 ){
                           newLeaves.add(newLeaf);
                       }
                   }
               }
               leaves = newLeaves;
           }
           
           return leaves;
           
       }
   }

   ​