[LeetCode 310] Minimum Height Tr

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 :
Input: n = 4, edges = [[1, 0], [1, 2], [1, 3]]

    0
    |
    1
   / \
  2   3 

Output: [1]

Example 2 :
Input: n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

 0  1  2
  \ | /
    3
    |
    4
    |
    5 

Output: `[3, 4]

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: 剥洋葱！

1. 尝试过的解法是： 遍历的点，以每个点都当做根节点算出高度，然后找出最小的。 但是如果数据大了会超时！！！
2. 剥洋葱法： 一层一层的褪去叶节点，最后剩下一个或两个节点就是最小高度树的根节点。
3. 需要建一个图HashMap <Integer, List<Integer>> ，每个节点都保存与其相连的所有点。
4. 遍历这个图，把所有只有一个连接边的节点都存入queue中，然后从queue中依次取出节点，通过图来找到和其相连的节点，并且在其相连节点的集合中将该叶节点删去。
   • 如果删完后此节点也变成一个叶节点了，加入queue，再下一轮删除。
   • 结束条件，当queue.size () <= 2时停
   • 最后queue中剩下的点，就是结果：

class Solution {
    /**************** Solution DFS ---- TIME OUT!!!!! -------------------
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) {
            List<Integer> result = new ArrayList<> ();
            result.add (0);
            return result;
        }
        
        if (edges == null || edges.length == 0 || edges[0].length == 0)
             return new ArrayList<> ();
        
        List<Integer> result = new ArrayList<> ();
        
        // generate graph
        Map<Integer, List<Integer>> tracker = new HashMap<> ();
        for (int i = 0; i < edges.length; i++) {
            List<Integer> neighbors = tracker.getOrDefault (edges[i][0], new ArrayList<> ());
            neighbors.add (edges[i][1]);
            tracker.put (edges[i][0], neighbors);
            
            neighbors = tracker.getOrDefault (edges[i][1], new ArrayList<> ());
            neighbors.add (edges[i][0]);
            tracker.put (edges[i][1], neighbors);
        }
        
        //2. get all heights
        Map<Integer, Integer> minNodeVsHeight = new HashMap<> ();
        int miniHeight = Integer.MAX_VALUE;
        
        for (int i = 0; i < n; i++) {
            int[] visited = new int[n];
            int[] longestPath = { 0 };
            int height = findMinHeightTreesHelper (tracker, visited, i, 1, longestPath);
            System.out.println (height);
            
            if (height < miniHeight) {
                result.clear ();
                result.add (i);
                miniHeight = height;
            } else if (height == miniHeight) {
                result.add (i);
            }
        }
        
        return result;
    }
    
    public int findMinHeightTreesHelper (Map<Integer, List<Integer>> tracker, int[] visited, int currentNode, int currentDepth, int[] longestPath) {
        if (visited[currentNode] != 0) {
            return 0;
        }
        
        visited[currentNode] = 1;
        longestPath[0] = Math.max (longestPath[0], currentDepth);
        
        for (int neighbor : tracker.get (currentNode)) {
            if (visited[neighbor] == 1) {
                continue;
            }
            
            findMinHeightTreesHelper (tracker, visited, neighbor, currentDepth + 1, longestPath);
        }
        
        return longestPath[0];
    }
    ************************* Solution END*****************/
    
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) {
            List<Integer> result = new ArrayList<> ();
            result.add (0);
            return result;
        }
        
        if (edges == null || edges.length == 0 || edges[0].length == 0)
             return new ArrayList<> ();
        
        List<Integer> result = new ArrayList<> ();
        
        // generate graph
        Map<Integer, List<Integer>> tracker = new HashMap<> ();
        for (int i = 0; i < edges.length; i++) {
            List<Integer> neighbors = tracker.getOrDefault (edges[i][0], new ArrayList<> ());
            neighbors.add (edges[i][1]);
            tracker.put (edges[i][0], neighbors);
            
            neighbors = tracker.getOrDefault (edges[i][1], new ArrayList<> ());
            neighbors.add (edges[i][0]);
            tracker.put (edges[i][1], neighbors);
        }
        
        // find all node which only connect to one node and push into the queue
        Queue<Integer> queue = new LinkedList<> ();
        for (Map.Entry<Integer, List<Integer>> entry : tracker.entrySet ()) {
            if (entry.getValue ().size () == 1) {
                queue.offer (entry.getKey ());
            }
        }
        
        // pilling the onion
        Queue<Integer> queue2 = new LinkedList<> ();
        int size = queue.size ();
        
        while (n > 2) {
            int currentNode = queue.poll ();
            int neighbor = tracker.get (currentNode).get(0);
            
            List<Integer> existedList = tracker.get (neighbor);
            existedList.remove (existedList.indexOf (currentNode));
            
            if (existedList.size () == 1) {
                queue2.offer (neighbor);
            }
            
            if (queue.isEmpty ()) {
                n = n - size;
                queue = queue2;
                queue2 = new LinkedList<> ();
                size = queue.size ();
            }
        }
        
        while (!queue.isEmpty ()) {
            result.add (queue.poll ());
        }
        
        return result;
    }
    
}