最小高度树

难度:

标签:

题目描述

树是一个无向图，其中任何两个顶点只通过一条路径连接。换句话说，任何一个没有简单环路的连通图都是一棵树。

给你一棵包含 n 个节点的树，标记为 0 到 n - 1 。给定数字 n 和一个有 n - 1 条无向边的 edges 列表（每一个边都是一对标签），其中 edges[i] = [a_i, b_i] 表示树中节点 a_i 和 b_i 之间存在一条无向边。

可选择树中任何一个节点作为根。当选择节点 x 作为根节点时，设结果树的高度为 h 。在所有可能的树中，具有最小高度的树（即，min(h)）被称为 最小高度树 。

请你找到所有的 最小高度树 并按 任意顺序 返回它们的根节点标签列表。

树的高度是指根节点和叶子节点之间最长向下路径上边的数量。

示例 1：

输入：n = 4, edges = [[1,0],[1,2],[1,3]]
输出：[1]
解释：如图所示，当根是标签为 1 的节点时，树的高度是 1 ，这是唯一的最小高度树。

示例 2：

输入：n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]
输出：[3,4]

提示：

1 <= n <= 2 * 10⁴
edges.length == n - 1
0 <= a_i, b_i < n
a_i != b_i
所有 (a_i, b_i) 互不相同
给定的输入保证是一棵树，并且 不会有重复的边

代码结果

运行时间: 72 ms, 内存: 23.6 MB

// 题目思路：
// 同上，使用Java Stream API进行数据流处理。
// 流处理可以简化部分代码逻辑，尤其是在筛选和转换数据的步骤上。
// 1. 使用IntStream和Collectors来构建和操作邻接表。
// 2. 使用队列来进行层级遍历，逐层修剪叶子节点。
 
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
 
public class SolutionStream {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n == 1) return List.of(0);
        List<Set<Integer>> adj = IntStream.range(0, n)
                .mapToObj(i -> new HashSet<Integer>())
                .collect(Collectors.toList());
        Arrays.stream(edges).forEach(edge -> {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        });
        List<Integer> leaves = IntStream.range(0, n)
                .filter(i -> adj.get(i).size() == 1)
                .boxed()
                .collect(Collectors.toList());
        while (n > 2) {
            n -= leaves.size();
            leaves = leaves.stream()
                    .flatMap(i -> adj.get(i).stream())
                    .distinct()
                    .filter(i -> {
                        adj.get(i).removeAll(leaves);
                        return adj.get(i).size() == 1;
                    })
                    .collect(Collectors.toList());
        }
        return leaves;
    }
}

解释

方法:

该题解使用了BFS的思想。首先构建无向图的邻接表表示，并统计每个节点的度。然后将所有度为1的节点入队，每轮迭代中，将当前队列中的节点出队，更新其邻居节点的度，如果邻居节点的度变为1，则将其入队。最后一轮迭代得到的节点就是最小高度树的根节点。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆

在这个最小高度树的解法中，为什么选择从所有度为1的节点开始进行BFS？

▷

在寻找最小高度树的过程中，从所有度为1的节点（叶子节点）开始进行BFS有助于从树的外围向中心收缩。这种方式可以逐步剥离最外层的叶子节点，直到剩下的节点无法再继续剥离（通常是中心节点或中心连线），这些剩余的节点就是最小高度树的可能的根节点。从叶子节点开始可以有效避免选择较长分支的顶端，从而确保树的高度尽可能小。

🦆

题解中提到使用了BFS，但实际上这种特殊的BFS操作（从外围向中心压缩）是否有一个特定的名称或者类似的问题解法？

▷

这种从外围向中心压缩的BFS操作通常被称为层次剥离法（Layer Peeling）或拓扑排序。在图理论中，这种方法经常用于寻找图的核心或中心层，特别适用于解决最小高度树（Minimum Height Trees）问题。这种方法通过逐层削减叶子节点，逼近图的中心，最终找到使得树高度最小的根节点。

🦆

如何确保在最后一轮迭代中得到的节点确实代表了最小高度树的根？

▷

通过逐渐剥离每层的叶子节点，直到不能再剥离为止，最后剩下的一层或几个节点就是图的中心层。这些节点是最后无法被进一步剥离的节点，因为它们互相连接，形成图的核心。在树或图的结构中，这些核心节点位于所有可能路径的大致中间点，因此从这些节点生成的树将具有最小的高度。这是因为从核心向外延伸的路径长度大致相等，从而保证了树的高度最小。

🦆

在构建无向图邻接表和度数组时，有没有可能出现重复边或自环，如果有，这种情况该如何处理？

▷

在构建无向图的邻接表和度数组时，理论上应该避免重复边和自环，因为它们可能会影响度的计算和BFS的正确性。在实现时，可以通过检查在添加边之前是否已经存在相同的边来避免重复边。对于自环，通常在无向图或树的结构中不应存在，如果输入数据包含自环，应该在读入数据时予以忽略或报错，因为自环在树的结构中没有实际意义。

相关问题

课程表

你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。

在选修某些课程之前需要一些先修课程。先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [a_i, b_i] ，表示如果要学习课程 a_i 则必须先学习课程 b_i。

例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。

请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。

示例 2：

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false
解释：总共有 2 门课程。学习课程 1 之前，你需要先完成课程 0 ；并且学习课程 0 之前，你还应先完成课程 1 。这是不可能的。

提示：

1 <= numCourses <= 2000
0 <= prerequisites.length <= 5000
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
prerequisites[i] 中的所有课程对 互不相同

课程表 II

现在你总共有 numCourses 门课需要选，记为 0 到 numCourses - 1。给你一个数组 prerequisites ，其中 prerequisites[i] = [a_i, b_i] ，表示在选修课程 a_i 前必须先选修 b_i 。

例如，想要学习课程 0 ，你需要先完成课程 1 ，我们用一个匹配来表示：[0,1] 。

返回你为了学完所有课程所安排的学习顺序。可能会有多个正确的顺序，你只要返回 任意一种 就可以了。如果不可能完成所有课程，返回 一个空数组 。

示例 1：

输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]
解释：总共有 2 门课程。要学习课程 1，你需要先完成课程 0。因此，正确的课程顺序为 [0,1] 。

示例 2：

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]
解释：总共有 4 门课程。要学习课程 3，你应该先完成课程 1 和课程 2。并且课程 1 和课程 2 都应该排在课程 0 之后。
因此，一个正确的课程顺序是 [0,1,2,3] 。另一个正确的排序是 [0,2,1,3] 。

示例 3：

输入：numCourses = 1, prerequisites = []
输出：[0]

提示：

1 <= numCourses <= 2000
0 <= prerequisites.length <= numCourses * (numCourses - 1)
prerequisites[i].length == 2
0 <= a_i, b_i < numCourses
a_i != b_i
所有[a_i, b_i] 互不相同

买卖股票的最佳时机含冷冻期稀疏矩阵的乘法