【树中最长路径】最小高度树

最小高度树

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

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

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

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

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

搜索树中最长路径，返回中点即可

但搜索最长路径是有技巧的：只需要先以任意节点为根，搜索最远的点x，再以x为根，搜索最远的点y，最长路径即x-y。搜索过程中记录parent数组，即可找回这条路径的中点。

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        // convert to G
        vector<vector<int>> G(n, vector<int>());
        for (auto& e: edges) {
            G[e[0]].push_back(e[1]);
            G[e[1]].push_back(e[0]);
        }
        // bfs
        vector<int> p(n); // parent
        auto bfs = [&] (int r) {
            for (int i = 0; i < n; i++) p[i] = -1; // -1 means not visited
            queue<pair<int, int>> q;
            q.emplace(r, 0);
            p[r] = -2; // just a number to d from -1 and non-neg node id.
            int mxd = 0;
            int mxi = r;
            while (!q.empty()) {
                auto [x, d] = q.front(); q.pop();
                if (d > mxd) {
                    mxd = d;
                    mxi = x;
                }
                for (int y: G[x]) {
                    if (p[y] == -1) {
                        p[y] = x;
                        q.emplace(y, d + 1);
                    }
                }
            }
            return mxi;
        };
        // find longest path
        int x = bfs(0);
        int y = bfs(x);
        // retrieve middle node
        vector<int> path;
        while (y != -2) {
            path.push_back(y);
            y = p[y];
        }
        int l = path.size();
        if (l % 2 == 0) return {path[l/2 - 1], path[l/2]};
        else return {path[l/2]};
    }
};