跟踪树与图形节点的最小高度

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

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

一个可能的实现(从教程点(是在每一步删除"叶子"。

希望在最后，只剩下中间人了。

下面是一个 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]]))