Poison

310. Minimum Height Trees

发表于
DFS(TLE)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Set<Integer>> nodeToNodeSetMap = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            nodeToNodeSetMap.add(new HashSet<>());
        }

        for (int[] edge : edges) {
            int nodeA = edge[0];
            int nodeB = edge[1];
            nodeToNodeSetMap.get(nodeA).add(nodeB);
            nodeToNodeSetMap.get(nodeB).add(nodeA);
        }

        int minHeight = Integer.MAX_VALUE;
        List<Integer> minHeightRootList = new ArrayList<>();
        Map<Integer, Integer> maxHeightCache = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int height = maxHeight(nodeToNodeSetMap, i, -1, maxHeightCache);
            if (height < minHeight) {
                minHeight = height;
                minHeightRootList.clear();
                minHeightRootList.add(i);
            } else if (height == minHeight) {
                minHeightRootList.add(i);
            }
        }

        return minHeightRootList;
    }

    private int maxHeight(List<Set<Integer>> nodeToNodeSetMap, int node, int from, Map<Integer, Integer> maxHeightCache) {
        int cacheKey = from * 20000 + node;
        Integer cachedMaxHeight = maxHeightCache.get(cacheKey);
        if (cachedMaxHeight != null) {
            return cachedMaxHeight;
        }

        int maxHeight = -1; // 注意高度为边的数量，即叶子节点高度为 0
        for (int to : nodeToNodeSetMap.get(node)) {
            if (to == from) {
                // 不走回头路，类似于二叉树不搜索父节点
                continue;
            }
            maxHeight = Math.max(maxHeight, maxHeight(nodeToNodeSetMap, to, node, maxHeightCache));
        }

        cachedMaxHeight = maxHeight + 1;
        maxHeightCache.put(cacheKey, cachedMaxHeight);
        return cachedMaxHeight;
    }
}
BFS + Topological Sort
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) {
            return Collections.singletonList(0);
        }
        
        int[] degrees = new int[n];
        List<Set<Integer>> nodeToNodeSetMap = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            nodeToNodeSetMap.add(new HashSet<>());
        }

        for (int[] edge : edges) {
            int nodeA = edge[0];
            int nodeB = edge[1];
            degrees[nodeA]++;
            degrees[nodeB]++;
            nodeToNodeSetMap.get(nodeA).add(nodeB);
            nodeToNodeSetMap.get(nodeB).add(nodeA);
        }

        Queue<Integer> leafNodeQueue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (degrees[i] == 1) {
                leafNodeQueue.offer(i);
            }
        }

        List<Integer> minHeightRootList = new ArrayList<>();

        while (!leafNodeQueue.isEmpty()) {
            minHeightRootList.clear();
            for (int i = leafNodeQueue.size(); i > 0; i--) {
                minHeightRootList.add(leafNodeQueue.poll());
            }

            for (int root : minHeightRootList) {
                for (int to : nodeToNodeSetMap.get(root)) {
                    degrees[to]--; // 切断与当前节点连接的边
                    if (degrees[to] == 1) { // 邻接节点是叶子节点
                        leafNodeQueue.offer(to);
                    }
                }
            }
        }

        return minHeightRootList;
    }
}
Reference

310. Minimum Height Trees