对于一个具有树特征的无向图，我们可选择任何一个节点作为根。图因此可以成为树，在所有可能的树中，具有最小高度的树被称为最小高度树。给出这样的一个图，写出一个函数找到所有的最小高度树并返回他们的根节点。
格式
该图包含 n 个节点，标记为 0 到 n - 1。给定数字 n 和一个无向边 edges 列表（每一个边都是一对标签）。
你可以假设没有重复的边会出现在 edges 中。由于所有的边都是无向边， [0, 1]和 [1, 0] 是相同的，因此不会同时出在 edges 里。
示例 1:
输入: n = 4, edges = [[1, 0], [1, 2], [1, 3]] 0 | 1 / \ 2 3 输出: [1] 1. 两次深度搜索 2. 搜索过程中记录d1[i]、d2[i]、up[i]、p[i] 3. d1[i] : 代表从i节点开始向下能够走的最远距离 4. d2[i] : 代表从i节点开始向下能够走的除最远之外的最远距离,d2[i] 可能与 d1[i] 相同 5. up[i] : 代表从i节点开始向上能够走的最远距离 6. p[i] : 代表从i节点向下走最远距离的路径中 i往下的第一个节点是节点p[i] class Solution { public: vector<vector<int>> g; vector<int> d1, d2, p1, up; void dfs1(int u, int father) { for (int x: g[u]) { if (x == father) continue; dfs1(x, u); int d = d1[x] + 1; if (d >= d1[u]) { d2[u] = d1[u], d1[u] = d; p1[u] = x; // p[]的作用是记录从节点u往下的最长路径是通过x这个子节点的 } else if (d > d2[u]) { d2[u] = d; } } } void dfs2(int u, int father) { for (int x: g[u]) { if (x == father) continue; if (p1[u] == x) up[x] = max(up[u], d2[u]) + 1; else up[x] = max(up[u], d1[u]) + 1; dfs2(x, u); } } vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) { g.resize(n); d1 = d2 = p1 = up = vector<int>(n); for (auto e: edges) { int a = e[0], b = e[1]; g[a].push_back(b), g[b].push_back(a); } dfs1(0, -1); dfs2(0, -1); int mind = n + 1; for (int i = 0; i < n; i ++ ) mind = min(mind, max(up[i], d1[i])); // 枚举每个节点,使其成为根节点,并计算根节点到叶子叶子节点的最大距离 vector<int> res; for (int i = 0; i < n; i ++) if (max(up[i], d1[i]) == mind) res.push_back(i); return res; } };
