java - 跟踪图节点的树的最小高度

Question

我正在尝试解决 Leetcode 的算法问题；称为“Minimum Height Trees”。

我尝试的是使用两种颜色(已访问，尚未访问)，然后递归调用辅助函数来增加高度。但我几乎在我注释掉的最后一步上有点卡住了。我无法想出一种方法来指定在什么条件下应该检查高度。

下面是我的代码。如果有人能帮助我，我很感激。 谢谢。

class Solution {
    enum Color{
        White,Grey;
    }
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        int minHeight = Integer.MAX_VALUE;
        List<List<Integer>> adjLists = buildGraph(n, edges);
        List<Integer> ret = new ArrayList<>();
        Color[] visited = new Color[n];
        Arrays.fill(visited, Color.White);

        for(int i = 0; i < n; i++){
            calculateHeight(adjLists, i, edges, visited, 0, ret);
        }

        return ret;

    }
        private List<List<Integer>> buildGraph(int n, int[][] edges){
            List<List<Integer>> adjLists = new ArrayList<>();
            for(int i = 0; i < n; i++){
                adjLists.add(new ArrayList<>());
            }
            for(int[] node : edges){
                int v = node[0], u = node[1];
                adjLists.get(u).add(v);
                adjLists.get(v).add(u); 
            }
            return adjLists;
        }
        private void calculateHeight(List<List<Integer>> adjLists, int start, int[][] edges, Color[] visited, int height, List<Integer> ret){
            /* I feel like I miss some conditions here but any idea is not top on my head for a week */
            if(visited[start] == Color.Grey)
                return;
            visited[start] = Color.Grey;
            for(int v : adjLists.get(start)){
                calculateHeight(adjLists, v, edges, visited, height+1, ret);
            }
            visited[start] = Color.White;
            return;
        }
    }
}

Answer 1

寻找最小高度树就是寻找树的中心(由一个或两个顶点组成)

一个可能的实现(来自 tutorialspoint )是在每一步中删除“叶子”。

希望最后只剩下中间部分。

下面是一个js示例

// https://www.tutorialspoint.com/centers-of-a-tree
function buildAdjencyList (edges) {
  return edges.reduce((dic, [from, to]) => {
    dic.set(from, (dic.get(from) || new Set()).add(to))
    dic.set(to, (dic.get(to) || new Set()).add(from))
    return dic
  }, new Map())
}
function simplify (G) {
  const verticesToDelete = []
  for (let [k,v] of G) {
    if (v.size == 1) {
      G.delete(k)
      verticesToDelete.push(k)
    }
  }
  for (let [k,v] of G) {
    verticesToDelete.forEach(del => {
      if (v.has(del)) {
        v.delete(del)
      }
    })
  }
}
function dump(G){
  for(let [k,v] of G){
    console.log(k, '->', JSON.stringify([...v]))
  }
}
function run(edges){
  const G = buildAdjencyList(edges)
  while(true){
    const keys = [...G.keys()]
    simplify(G)
    // handles bicentral tree
    if(G.size === 0) {
      return keys
    }
    // handles central tree
    if(G.size === 1) {
      return [...G.keys()]
    }
    console.log('iter')
    dump(G)
  }
}

console.log('bicentral', run([[0, 1], [1, 2], [3, 2], [2, 4], [2, 5],[5,6],[6,7]]))
console.log('central', run([[0, 1], [1, 2]]))