的求解非常简单, 直接递归即可. 我们用邻接列表表示图, G[i] 为节点 i 的邻接节点列表. 我们将结果保存在数组 C 中.
1 2 3 4 5 6 7 8
intchildren(const vector<vector<int>> &G, int i, int pi, vector<int> &C){ int ans = 0; for (int j : G[i]) { if (j == pi) continue; ans = max(ans, children(G, j, i, C) + 1); } return C[i] = ans; }
C++
上面的代码中, 对于叶子节点, 由于没有子节点, ans 在 for 循环后仍然为 0. 对于其他节点, C[i] 等于其结果最大的子节点加 1.
intchildren(const vector<vector<int>> &G, int i, int pi, vector<int> &C, vector<int> &C1, vector<int> &mc){ int m = 0, n = 0, c = -1; // m 为最远节点的距离, n 为第二远节点的距离. for (int j : G[i]) { if (j == pi) continue; int l = children(G, j, i, C, C1, mc) + 1; if (l >= m) { n = m, m = l; c = j; } elseif (l > n) { n = l; } } C[i] = m, C1[i] = n; mc[i] = c; return m; }
voidparents(const vector<vector<int>> &G, int i, int pi, vector<int> &C, vector<int> &C1, vector<int> &mc, vector<int> &P){ if (pi >= 0) { P[i] = max(mc[pi] == i ? C1[pi] : C[pi], P[pi]) + 1; // (3) 式 } for (int j : G[i]) { if (j != pi) parents(G, j, i, C, C1, mc, P); } }
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges){ vector<vector<int>> G(n); for (constauto &edge : edges) { G[edge[0]].push_back(edge[1]); G[edge[1]].push_back(edge[0]); }
int d = n; for (int i = 0; i < n; ++i) d = min(d, max(C[i], P[i])); for (int i = 0; i < n; ++i) if (d == max(C[i], P[i])) ans.push_back(i); return ans; }