Отслеживать минимальную высоту дерева от узлов графа

Question

Я пытался решить вопрос об алгоритме из Leetcode; называется " Деревья минимальной высоты ".

Я пытался использовать 2 цвета (посещенные, еще не посещенные), а затем рекурсивно вызвать вспомогательную функцию для увеличения высоты. Но я немного застрял на последнем шаге, где я прокомментировал. Я не могу придумать, как указать, при каких условиях я должен проверять высоту.

Ниже приведен мой код. Если кто-нибудь может мне помочь, я ценю. Спасибо.

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]]))