【图论题典】Swift 解 LeetCode 最小高度树：中心剥离法详解

摘要

树是一种重要的数据结构，在许多应用里，我们希望选一个根，让这棵树的高度最小。LeetCode 310 就是这样一道题：给你无向树结构，选出所有可能成为“最小高度根”的节点。本文用 Swift 实现专业级解法，附上可运行代码、过程图解和复杂度分析，让你从思路到实现完全掌握。这对理解中枢化图结构、分层遍历特别有帮助，既能用于面试，也有真实网络或社交分析场景借鉴价值。

描述

题目定义：给定 n 个节点和 n–1 条无向边，它构成一棵树（连通且无环）。我们可以任选一个节点作为根，这样就有一个高度；求所有能使树高度最小的根节点。

几个入门例子：

• n = 4, edges = [[1,0],[1,2],[1,3]]，根选 1 时高度是 1，是最小的，答案 [1]
• n = 6, edges = [[3,0],[3,1],[3,2],[3,4],[5,4]]，答案 [3,4]，两者都是中心节点

这道题通过连续“剥离”叶子节点的办法，能高效找到中心节点。

题解答案

func findMinHeightTrees(_ n: Int, _ edges: [[Int]]) -> [Int] {guard n > 1 else { return [0] }var adj = Array(repeating: [Int](), count: n)var degree = Array(repeating: 0, count: n)for e in edges {adj[e[0]].append(e[1])adj[e[1]].append(e[0])degree[e[0]] += 1degree[e[1]] += 1}var leaves = [Int]()for i in 0..<n where degree[i] == 1 {leaves.append(i)}var count = nwhile count > 2 {count -= leaves.countvar newLeaves = [Int]()for leaf in leaves {for nei in adj[leaf] {degree[nei] -= 1if degree[nei] == 1 { newLeaves.append(nei) }}}leaves = newLeaves}return leaves
}

这段代码直接运行就可返回最小高度树的所有根节点，非常简洁。

题解代码分析

思路来源：树的“中心剥离法”

1. 从树的叶子（度为 1）开始，逐层往内“剥离”节点。
2. 每剥掉一层叶子，就把剩余节点数减去。
3. 当剩下 ≤2 个节点时，它们就是树的中心（中点），即所求根。

这个过程类似处理拓扑排序，复杂度优雅。

构造邻接表和度数组

用 adj 存储邻居节点，degree 存储当前节点的度数，初始准备叶子。

循环剥叶子

每次把当前所有叶子节点剥掉，并更新它们邻居的度数；新的度为 1 的节点加入下一层叶子。

终止条件

剩余节点 ≤2 时，剥离结束。此时的 leaves 就是能成为最小高度树根的集合。

示例测试及结果

print(findMinHeightTrees(4, [[1,0],[1,2],[1,3]])) // 输出 [1]
print(findMinHeightTrees(6, [[3,0],[3,1],[3,2],[3,4],[5,4]])) // 输出 [3,4]
print(findMinHeightTrees(1, [])) // 输出 [0]
print(findMinHeightTrees(2, [[0,1]])) // 输出 [0,1]

以上示例覆盖了最小树、单节点、双节点等边界情况，验证结果都正确。

时间复杂度

• 构造图和度数：O(n)
• 剥离所有叶子：每个节点最多被剥一次，边最多处理一次，综合 O(n)

所以整体时间复杂度是 O(n)，非常高效，适合 n ~2×10⁴ 的场景。

空间复杂度

• 存图结构 adj: O(n)
• 存度数数组 degree: O(n)
• 临时叶子列表 leaves: O(n)（通常远小于 n）

总体空间复杂度是 O(n)。

总结

• 算法核心是找到树中心，通过 “多层剥叶” 思路解决，既直观又高效。

• 使用场景：

  • 在图论中求最短广播源点
  • 网络模块寻找延迟最低的通信节点
  • 社交网络中寻找信息传播中枢

• Swift 实现简洁明快，剥离过程逻辑清晰，适合算法面试与项目落地。