想要精通算法和SQL的成长之路 - 最小高度树

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 最小高度树

原题链接

从题目的含义中我们可以发现：

• 题目的树是一颗多叉树。
• 叶子节点的度为1，而非叶子节点的度至少是2（多叉树）
• 树的高度由根节点到叶子节点的最大距离决定。

题目要求返回根节点列表，那么我们很难自上而下的遍历。那么不妨我们从叶子节点入手，自下而上的遍历呢？

• 我们构建邻接表和一个度数组。
• 我们把度为1的节点（叶子节点）入队。
• 每层遍历，把队列中的节点移除，并根据邻接表拿到他们的相邻节点。并且更新他们的度（-1），若度在减1之后，为1，继续把他们丢到队列，进入下一层循环。
• 那么最终留下来的就是根节点列表。

1.1 邻接表的构建

// 构建邻接表和出度数组
List<List<Integer>> adj = new ArrayList<>();
for (int i = 0; i < n; i++) {
    adj.add(new ArrayList<>());
}
int[] degree = new int[n];
for (int[] edge : edges) {
	// 一条边的两个端点，都要计算度以及构建对应的邻接关系
    degree[edge[0]]++;
    degree[edge[1]]++;
    adj.get(edge[0]).add(edge[1]);
    adj.get(edge[1]).add(edge[0]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13

1.2 入度为1的先入队

// 出度为1的入队
LinkedList<Integer> queue = new LinkedList<>();
for (int i = 0; i < n; i++) {
    if (degree[i] == 1) {
        queue.offer(i);
    }
}
1
2
3
4
5
6
7

1.3 BFS遍历

while (!queue.isEmpty()) {
    // 清空数组，每层遍历，res存储的都是
    res.clear();
    int size = queue.size();
    for (int i = 0; i < size; i++) {
        // 从队列中移除一个度为1的元素并把它加入到结果集
        Integer cur = queue.poll();
        res.add(cur);
        // 根据当前元素，拿到与他的邻接元素
        List<Integer> nextNode = adj.get(cur);
        // 更新邻接元素的度，如果度-1之后，为1，说明它是新的叶子节点（老的我们直接删除），继续丢到队列，进入下一层循环
        for (Integer next : nextNode) {
            degree[next]--;
            if (degree[next] == 1) {
                queue.offer(next);
            }
        }
    }
}
// 到这里，res留下的就是根节点
return res;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

完整代码如下：

public class Test310 {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        ArrayList<Integer> res = new ArrayList<>();
        // 如果只有一个节点，直接返回根节点0
        if (n == 1) {
            res.add(0);
            return res;
        }
        // 构建邻接表和出度数组
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adj.add(new ArrayList<>());
        }
        int[] degree = new int[n];
        for (int[] edge : edges) {
            degree[edge[0]]++;
            degree[edge[1]]++;
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }
        // 出度为1的入队
        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (degree[i] == 1) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            // 清空数组，每层遍历，res存储的都是
            res.clear();
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                // 从队列中移除一个度为1的元素并把它加入到结果集
                Integer cur = queue.poll();
                res.add(cur);
                // 根据当前元素，拿到与他的邻接元素
                List<Integer> nextNode = adj.get(cur);
                // 更新邻接元素的度，如果度-1之后，为1，说明它是新的叶子节点（老的我们直接删除），继续丢到队列，进入下一层循环
                for (Integer next : nextNode) {
                    degree[next]--;
                    if (degree[next] == 1) {
                        queue.offer(next);
                    }
                }
            }
        }
        // 到这里，res留下的就是根节点
        return res;
    }
}
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