0310. Minimum Height Trees
==========================
题目信息
--------
:题号: 0310
:难度: Medium
:主题: 无向树、根节点选择、树高、结果集合
:原题: `LeetCode 0310 `_
:重点: 输入保证是一棵树、树高取根到最远叶节点的边数、返回全部最优根且顺序不限
题目重述
--------
有一棵包含 ``n`` 个节点的无向树,节点编号为 ``0`` 到 ``n-1``,边数组 ``edges`` 中每个 ``[a, b]`` 表示两个节点之间存在一条无向边。把任意节点选作根后,树的高度是根节点到最远叶节点路径上的边数。
返回所有能够使树高达到最小值的根节点编号,结果顺序不限。``n`` 位于 ``[1, 2 * 10^4]``;当 ``n > 1`` 时恰有 ``n-1`` 条边,端点合法、两端不同,输入没有重复边,并保证整体连通且无环。当 ``n == 1`` 时,边数组为空,唯一节点 ``0`` 就是答案。
自建示例
--------
树有两个同样优的中心:
.. code-block:: text
输入:n = 6,edges = [[0,1], [1,2], [2,3], [3,4], [4,5]]
输出:[2,3]
解释:以节点 2 或 3 为根时,最远节点距离都是 3;选择更靠近任一端点的节点都会得到更大的树高,输出顺序可以交换。
只有一个节点:
.. code-block:: text
输入:n = 1,edges = []
输出:[0]
解释:不存在边,节点 0 作为根时树高为 0,也是唯一选择。
从叶子向树心剥离
------------------
树的最小高度根只能位于树的直径中心:若根偏离中心,直径的一端会比另一端更远;向中心移动一层可以缩短较长的一侧而不会增加最远距离。因此答案最多有两个相邻节点,分别对应直径长度为偶数或奇数的情形。
可以反向寻找这些中心。第一层叶子是当前度数为 1 的节点;无论把根放在哪里,这些叶子都属于最外层。删去整层叶子后,剩余树的中心不变,继续删去新产生的叶子。每次必须整层删除,不能只删除队列中的一个,否则会破坏“按距离同步向内收缩”的含义。当剩余节点不超过两个时,它们就是全部最优根。
C++ 实现
--------
.. code-block:: cpp
class Solution {
public:
std::vector findMinHeightTrees(
int n, std::vector>& edges) {
if (n == 1) return {0};
std::vector> graph(n);
std::vector degree(n, 0);
for (const auto& edge : edges) {
graph[edge[0]].push_back(edge[1]);
graph[edge[1]].push_back(edge[0]);
++degree[edge[0]];
++degree[edge[1]];
}
std::queue leaves;
for (int node = 0; node < n; ++node) {
if (degree[node] == 1) leaves.push(node);
}
int remaining = n;
while (remaining > 2) {
int layerSize = static_cast(leaves.size());
remaining -= layerSize;
for (int i = 0; i < layerSize; ++i) {
int leaf = leaves.front();
leaves.pop();
for (int neighbor : graph[leaf]) {
if (--degree[neighbor] == 1) {
leaves.push(neighbor);
}
}
}
}
std::vector result;
while (!leaves.empty()) {
result.push_back(leaves.front());
leaves.pop();
}
return result;
}
};
代码分析
--------
度数数组记录删除叶子后邻居还剩多少条边;某个邻居度数降为 1 时,它恰好成为下一层叶子。树保证连通,所以队列在最后会保留一个或两个中心,``n == 1`` 单独返回是因为单节点没有度数为 1 的叶子。每条边只被处理有限次,时间复杂度为 ``O(n + |edges|)``,额外空间为 ``O(n + |edges|)``。