P161 高度最小的树

描述#

这个题目说的是，给你一个没有环的无向图，把图上任意一个节点当作根节点，就可以把它看作一棵树。这样一来，对于一个包含 n 个节点的无环无向图，可以产生 n 棵不同的树。你要找出这 n 棵树中，所有高度最小的树，并返回它们的根节点。其中，高度的定义是：根节点和最远的叶子节点之间，边的数量。

注意，给你的 n 是一个正整数，表示图上共有 n 个节点，编号从 0 到 n-1。另外给你一组数字对，表示连接两个节点的边。并且给你的这组数字对中，不包含重复的边。

比如说，给你的 n 等于 4，给你的表示边的数字对是：
[0, 1]，
[0, 2]，
[0, 3]
它表示这样一个无向图：
1
|
0
/ 

2   3
在这个无向图中，高度最小的树只有一棵，就是以 0 为根节点的树。于是返回：[0]。
如果把 n 改成 5，然后再加一条边 [3, 4]，这个无向图就会变成：
1
|
0
/ 

2   3
|
4
在这个无向图中，高度最小的树有两棵（高度为 2），返回它们对应的根节点是：[0, 3]。

代码#

public class AlgoCasts {

  private void dfs(List<List<Integer>> g, boolean[] visited,
                   int node, int dist, int[] max) {
    visited[node] = true;
    if (dist > max[0]) max[0] = dist;
    for (int v: g.get(node))
      if (!visited[v])
        dfs(g, visited, v, dist+1, max);
    visited[node] = false;
  }

  // Time: O(n^2), Space: O(n)
  public List<Integer> findMinHeightTreesBruteForce(int n, int[][] edges) {
    if (n == 1) return Collections.singletonList(0);
    List<List<Integer>> g = new ArrayList<>(n);
    for (int i = 0; i < n; ++i)
      g.add(new ArrayList<>());
    for (int[] e: edges) {
      g.get(e[0]).add(e[1]);
      g.get(e[1]).add(e[0]);
    }

    boolean[] visited = new boolean[n];
    int[] heights = new int[n];
    int[] max = new int[]{0};
    int minHeight = Integer.MAX_VALUE;
    for (int i = 0; i < n; ++i) {
      dfs(g, visited, i, 0, max);
      heights[i] = max[0];
      if (heights[i] < minHeight) minHeight = heights[i];
      max[0] = 0;
    }

    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < n; ++i)
      if (heights[i] == minHeight)
        result.add(i);
    return result;
  }

  // Time: O(n), Space: O(n)
  public List<Integer> findMinHeightTreesShrink(int n, int[][] edges) {
    if (n == 1) return Collections.singletonList(0);
    List<List<Integer>> g = new ArrayList<>(n);
    for (int i = 0; i < n; ++i)
      g.add(new ArrayList<>());
    for (int[] e: edges) {
      g.get(e[0]).add(e[1]);
      g.get(e[1]).add(e[0]);
    }

    int[] degree = new int[n];
    LinkedList<Integer> leaves = new LinkedList<>();
    for (int i = 0; i < n; ++i) {
      degree[i] = g.get(i).size();
      if (degree[i] == 1) leaves.add(i);
    }
    while (leaves.size() < n) {
      int size = leaves.size();
      n -= size;
      for (int i = 0; i < size; ++i) {
        int leaf = leaves.poll();
        for (int v: g.get(leaf)) {
          --degree[v];
          if (degree[v] == 1) leaves.add(v);
        }
      }
    }
    return leaves;
  }

}