310. Minimum Height Trees.md

310. Minimum Height Trees

---

leetcode Daily Challenge on November 4th, 2020.

---

Difficulty : Medium

Related Topics : BFS、Graph

---

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

• mine
  • Java

    • DFS & MEMO Runtime: 68 ms, faster than 10.45%, Memory Usage: 48.4 MB, less than 5.49% of Java online submissions

      // O(N * D)time  D is the max height
      // O(N)space
      Map<String,Integer> memo;
      public List<Integer> findMinHeightTrees(int n, int[][] edges) {
          memo = new HashMap<>();
          List<Integer>[] arr = new List[n];
          for (int i = 0; i < n; i++) {
              arr[i] = new ArrayList<>();
          }
          for (int[] edge : edges) {
              arr[edge[0]].add(edge[1]);
              arr[edge[1]].add(edge[0]);
          }
          List<Integer> res = new LinkedList<>();
          boolean[] used = new boolean[n];
          int depth = Integer.MAX_VALUE;
          for (int i = 0; i < n; i++) {
              int d = dfs(arr, used, i, 1);
              if (d <= depth) {
                  if (d < depth) {
                      depth = d;
                      res.clear();
                  }
                  res.add(i);
              }
          }
          return res;
      }
      
      int dfs(List<Integer>[] arr, boolean[] used, int i, int depth) {
          int res = 0;
          used[i] = true;
          for (int j : arr[i]) {
              String key = i + "-" + j;
              int d;
              if (used[j]) {
                  d = 0;
                  memo.put(j + "-" + i, depth);
              } else if (memo.containsKey(key)) {
                  d = memo.get(key);
              } else {
                  d = dfs(arr, used, j, depth + 1);
                  memo.put(key, d);
              }
              res = Math.max(res, d);
          }
          used[i] = false;
          return res + 1;
      }
      

    • Topological Sort Runtime: 10 ms, faster than 93.56%, Memory Usage: 44.2 MB, less than 29.67% of Java online submissions

      // O(N)time
      // O(N)space
      public List<Integer> findMinHeightTrees(int n, int[][] edges) {
          LinkedList<Integer> res = new LinkedList<>();
          if(n == 1){
              res.add(0);
              return res;
          }
          List<Integer>[] arr = new List[n];
          for (int i = 0; i < n; i++) {
              arr[i] = new ArrayList<>();
          }
          for (int[] edge : edges) {
              arr[edge[0]].add(edge[1]);
              arr[edge[1]].add(edge[0]);
          }
          int count = n;
          for (int i = 0; i < n; i++) {
              if (arr[i].size() == 1) {
                  res.add(i);
                  count--;
              }
          }
          while (!res.isEmpty() && count > 0) {
              int size = res.size();
              for(int k = 0; k < size; k++){
                  int remove = res.removeFirst();
                  for (int i : arr[remove]) {
                      arr[i].remove((Object) remove);
                      if (arr[i].size() == 1) {
                          res.add(i);
                          count--;
                      }
                  }
              }
          }
          return res;
      }
      

---