# 310. 最小高度树 (Medium)

## 问题描述
[310. 最小高度树][link] (Medium)

[link]: https://leetcode.cn/problems/minimum-height-trees/

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

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

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

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

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

**示例 1：**

![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-065433.jpg)

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

**示例 2：**

![](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-065435.jpg)

```
输入：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](https://pic-upyun.zwyyy456.tech/smms/2023-12-26-065437.jpg)

首先，我们以节点 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$。

## 代码

```cpp
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;
    }
};
```