参考文献
lt ref{:target=”_blank”}
ref{:target=”_blank”}
暴力解法是O(n^2),分别计算每个点的最小高度
树形dp优化后,2遍dfs,对于0号节点为root的树
dfs1: 自下向上,计算每个节点最大高度和次高度
dfs2: 自上向下,计算每个节点的高度
d1是比较容易计算的,这里up有两种情况,所以其实一个点的高度就是如下3种情况之一
C++ 代码
class Solution {
public:
// d1 最大高度,d2 次大高度(非严格小于d1)
// p1 表示u最大高度的贡献子节点,用于判断
// up 表示u向上(父节点方向)的最大高度
vector<int> d1, d2, p1, up;
unordered_map<int, unordered_set<int>> graph_;
void dfs1(int u, int fa){
for(int t : graph_[u]){
// 不用向上回溯
if(t == fa)continue;
dfs1(t, u);
int dis = d1[t] + 1;
if(dis > d1[u]){
// update 最大高度 和 次大高度
d2[u] = d1[u];
d1[u] = dis;
p1[u] = t;
} else if(dis > d2[u]){
d2[u] = dis;
}
}
}
void dfs2(int u, int fa){
for(int t : graph_[u]){
if(t == fa)continue;
if(t == p1[u]){
// 使用次大高度
up[t] = 1 + max(up[u], d2[u]);
} else {
// 使用最大高度
up[t] = 1 + max(up[u], d1[u]);
}
dfs2(t, u);
}
}
vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
d1.resize(n);
d2.resize(n);
p1.resize(n);
up.resize(n);
for(const auto& e : edges){
int a = e[0], b = e[1];
graph_[a].insert(b);
graph_[b].insert(a);
}
dfs1(0, -1);
dfs2(0, -1);
// 寻找最小
int min_dis = INT_MAX;
for(int i=0; i<n; ++i)min_dis = min(min_dis, max(d1[i], up[i]));
vector<int> res;
for(int i=0; i<n; ++i){
if(max(d1[i], up[i]) == min_dis)res.push_back(i);
}
return res;
}
};