310-最小高度树

LeetCode 310. 最小高度树

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

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

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

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

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

示例 1：

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

method

先求从任意节点开始的一条最长路径，末尾为x，再求从x开始的一条最长路径，末尾为y，从x到y的路径上的节点记为$p_1 \rightarrow p_2\rightarrow \ldots \rightarrow p_m$，最长路径长度为$m-1$

• $m$为偶数，最小高度树的根节点为$p_{\frac{m}{2}}$或$p_{\frac{m}{2}+1}$，最小高度为$\frac{m}{2}$
• $m$为奇数，最小高度树的根节点为$p_{\frac{m+1}{2}}$，最小高度为$\frac{m-1}{2}$

int findLongest(int s, vector<vector<int>>& edge, vector<int>& fa) {
    int n = edge.size();
    vector<bool> used(n, false);    // 双向边需要标记
    queue<int> q;
    q.push(s);
    used[s] = true;
    int node = -1;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        node = x;   // 找到最后出队的那个节点
        for (auto& e : edge[x]) {
            if (!used[e]) {
                used[e] = true;
                q.push(e);
                fa[e] = x;
            }
        }
    }
    return node;
}
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
    vector<vector<int>> edge(n);
    for (auto& e : edges) {
        edge[e[0]].push_back(e[1]);
        edge[e[1]].push_back(e[0]);
    }
    vector<int> fa(n, -1);
    int x = findLongest(0, edge, fa);   // 这里任意节点用0
    int y = findLongest(x, edge, fa);   // 这次的fa数组才有用
    fa[x] = -1; // 祖先节点的fa设为-1
    vector<int> path;
    while (y != -1) {
        path.push_back(y);  // 记录x->y路径上的点
        y = fa[y];
    }
    int m = path.size();
    if (m % 2 == 0) {   // 这里是从0开始
        return {path[m / 2 - 1], path[m / 2]};  // 偶数中间那两个
    }
    else {
        return {path[m / 2]};   // 奇数就是中间那个
    }
}