leetcode MinimumHeightTrees
z
 2019-04-09 10:36:27   
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import java.util.*;

public class MinimumHeightTrees {
  /**
   * 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.
   */
  public List<Integer> findMinHeightTrees(int n, int[][] edges) {

    if (n == 1) {
      return Arrays.asList(0);
    }

    // get adjust neighbor
    HashMap<Integer, LinkedList<Integer>> adj = new HashMap<>(); // adj
    int[] indegree = new int[n];
    for (int i=0; i<n; i++)
      adj.put(i, new LinkedList<>());
    for (int[] e: edges){
      adj.get(e[0]).add(e[1]);
      adj.get(e[1]).add(e[0]);
      indegree[e[1]] ++;
      indegree[e[0]] ++;
    }

    // get leave nodes
    ArrayList<Integer> leaves = new ArrayList<>();

    for (int i=0; i<n; i++){
      if (indegree[i] == 1){
        leaves.add(i);
      }
    }


    while(n>2){
      ArrayList<Integer> nextLeave = new ArrayList<>();
      for (int leave: leaves){
        for (int node: adj.get(leave)){
          if (--indegree[node] == 0)
            nextLeave.add(node);
        }
      }
      n -= leaves.size();
      leaves = nextLeave;
    }
    return leaves;
  }
}