LeetCode-310. 最小高度树-Java-medium

题目链接

法一（BFS）

    /**
     * 法一（BFS）
     * 1. 思路
     * （1）最长路径的中间节点就是最小高度树的根节点
     * （2）反向BFS，从叶节点向根节点，一层一层剥离，最后留下的就是最中间的节点
     * 2. 注意
     * （1）本题给定图没有环，即任意两个节点之间有且仅有一条路径
     * （2）树中的共有n-1条不同的边
     * （3）叶子节点的度为1，非叶子节点的度至少为2
     * （4）树的高度由根节点到叶子节点的最大距离决定
     * 3. 复杂度
     * （1）时间复杂度：O(n)
     * （2）空间复杂度：O(n)
     *
     * @param n
     * @param edges
     * @return
     */
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> ans = new ArrayList<>();
        if (n == 1) { // 如果只有一个节点，那么他就是最小高度树根节点
            ans.add(0);
            return ans;
        }

        int[] degree = new int[n]; // 存储各个节点的度
        List<Integer>[] adj = new List[n]; // 利用邻接表存储图关系
        for (int i = 0; i < n; i++) {
            adj[i] = new ArrayList<>(); // 初始化邻接表
        }
        for (int[] edge : edges) {
            degree[edge[0]]++; // 每个节点对应的度+1
            degree[edge[1]]++;
            adj[edge[0]].add(edge[1]); // edges转邻接表，无向边要连接两次
            adj[edge[1]].add(edge[0]);
        }

        boolean[] visited = new boolean[n]; // 记录当前节点是否已被访问
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) { // 把所有出度为1的节点，也就是叶子节点入队
            if (degree[i] == 1) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) { // 反向BFS，从叶节点开始，往根BFS
            ans.clear(); // 每层循环都要清空上一次保存的结果，从外圈到内圈，每圈是一个ans，最后一圈就是结果
            int size = queue.size(); // 当前层的节点数量（当前所有叶节点为一层）
            for (int i = 0; i < size; i++) {
                int cur = queue.poll(); // 剪去当前层叶子节点，从而露出新的叶子节点
                ans.add(cur); // 将当前层节点加入ans，按照这里层的定义，若存在多棵最小高度树，这些树的根会划为同一层
                visited[cur] = true; // 把当前层访问的叶子节点标记为true
                degree[cur]--; // 当前访问的叶子节点度-1
                List<Integer> neighbors = adj[cur]; // 当前访问叶子节点的所有邻接点
                for (int neighbor : neighbors) { // 遍历所有邻接点
                    if (visited[neighbor]) { // 遇到低层的节点则直接跳过（因为是从下往上BFS，下面的就不必再遍历）
                        continue;
                    }
                    degree[neighbor]--; // 当前邻接点度-1，相当于断开了与叶子节点的联系
                    if (degree[neighbor] == 1) { // 如果当前邻接点变为了新的叶子节点就入队
                        queue.offer(neighbor);
                        break; // 对于当前节点，只能有一个特定的父节点，找到这一个就可以不用再遍历邻接表了
                    }
                }
            }
        }
        return ans; // 返回最后一圈的ans
    }
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
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

本地测试

        /**
         * 310. 最小高度树
         */
        lay.showTitle(310);
        Solution310 sol310 = new Solution310();
        int[][] edges310 = new int[][]{{1, 0}, {1, 2}, {1, 3}};
        arrayOpt.showIntTwoDimArray(edges310, edges310.length);
        System.out.println(sol310.findMinHeightTrees(4, edges310));
1
2
3
4
5
6
7
8