问题描述 链接到标题

310. 最小高度树 (Medium)

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

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

可选择树中任何一个节点作为根。当选择节点 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ᵢ, bᵢ < n
  • aᵢ != bᵢ
  • 所有 (aᵢ, bᵢ) 互不相同
  • 给定的输入 保证 是一棵树，并且 不会有重复的边

解题思路 链接到标题

5KgtDT37MY1UexW

首先，我们以节点 0 为根结点，计算出每个子树的最大高度 $f$。即 $f(pa)$ 表示以结点 pa 为根结点的子树的最大高度，$f(u)$ 表示以结点 u 为根结点的子树的最大高度。

那么，以 u 为根结点的子树的最大高度，由以下几个值的最大值取得：

  • 以 u 为根结点的子树的最大高度，即 $f(u)$，这个是当前树结构下，u 往子结点的方向所能取到的最大高度；
  • u 向父结点，即 pa 的方向所能取到的最大高度，记为 $g(u)$；
    • $g(pa) + 1$，即 pa 往它的父结点的方向所能取到的最大高度；
    • pa 向下（但是不往 u 的方向）所能取到的最大高度 $h_{pa}$；
      • 如果 $f(pa)$ 是由 pa 到 u 的方向取得的，那么 $h_{pa} = f_2(pa) + 1$
      • 否则 $h_{pa} = f(pa) + 1$

其中，$f_2(pa)$ 表示以 pa 为根结点的子树的次大高度，这里我们要求次大高度对应的 pa 的子结点与最大高度对应的子结点不能是同一个子结点，因此我们在求 $f$ 的时候，必须记录 $f(pa)$ 由哪个子结点取得，同时我们还要求 $f_2$。

即如果 pa 只有一个子结点 u，那么 $f_2(pa) = 1$，$f(pa) = f(u) + 1$。

代码 链接到标题 

class Solution {
  public:
    using pii = pair<int, int>;
    pii geth(vector<vector<int>> &graph, int parent, vector<int> &max_idx, int cur, vector<pii> &heights) {
        int hmx = 1, hnd = 0; // 最大值与次大值
        for (int idx : graph[cur]) {
            if (idx == parent) {
                continue;
            }
            auto [h1, h2] = geth(graph, cur, max_idx, idx, heights);
            if (h1 + 1 >= hmx) {
                hnd = hmx;
                hmx = h1 + 1;
                max_idx[cur] = idx;
            } else if (h1 + 1 >= hnd) {
                hnd = h1 + 1;
            }
        }
        heights[cur] = {hmx, hnd};
        return {hmx, hnd};
    }
    void bfs(vector<vector<int>> &graph, int parent, vector<int> &max_idx, int cur, vector<pii> &heights, vector<int> &res) {
        queue<tuple<int, int, int>> q;
        q.push({0, heights[0].first, 1});
        vector<int> vis(graph.size());
        vis[0] = 1;
        while (!q.empty()) {
            auto [idx, f_idx, g_idx] = q.front();
            res[idx] = max(res[idx], max(f_idx, g_idx));
            q.pop();
            // 还需要一个 visit 数组
            for (int next : graph[idx]) {
                if (vis[next] == 1) {
                    continue;
                }
                vis[next] = 1;
                int gpa = 0;
                if (max_idx[idx] == next) { // 最大值从 next 取到
                    gpa = heights[idx].second + 1; // 次大值 + 1
                } else {
                    gpa = heights[idx].first + 1;
                }
                q.push({next, heights[next].first, max(g_idx + 1, gpa)});
                // cout << next << " " << heights[next].first << " " << g_idx + 1 << " " << gpa << endl;
            }
        }
    }
    vector<int> findMinHeightTrees(int n, vector<vector<int>> &edges) {
        // 求一个根结点的最大高度和次大高度
        vector<vector<int>> graph(n);
        for (auto &vec : edges) {
            graph[vec[0]].push_back(vec[1]);
            graph[vec[1]].push_back(vec[0]);
        }
        vector<pii> heights(n);
        vector<int> max_idx(n);
        geth(graph, 0, max_idx, 0, heights);
        vector<int> res(n);
        bfs(graph, 0, max_idx, 0, heights, res);
        int min_res = 1e5;
        for (int i = 0; i < n; ++i) {
            min_res = min(min_res, res[i]);
        }
        cout << endl;
        vector<int> ans;
        for (int i = 0; i < n; ++i) {
            if (res[i] == min_res) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};