做网站加模块,怎样做网站营销,怎么做有图有声的网站,二手房网站开发背景题目链接
最小高度树 思路#xff1a;本质上是找到树中的最长路径。当最长路径上中间点#xff08;若路经长为偶数#xff0c;则中间点仅有一个#xff0c;否者中间点有两个#xff09;作为根时#xff0c;此时树高最小。 Code:
class Solution {
public://拓扑排序int…题目链接
最小高度树 思路本质上是找到树中的最长路径。当最长路径上中间点若路经长为偶数则中间点仅有一个否者中间点有两个作为根时此时树高最小。 Code:
class Solution {
public://拓扑排序int d[20010];queuepairint,int q;vectorint e[20010];bool vis[20010];vectorpairint,int res;vectorint findMinHeightTrees(int n, vectorvectorint edges) {vectorint ans;if(n1) {ans.push_back(0);return ans;}for(int i0;iedges.size();i) {e[edges[i][0]].push_back(edges[i][1]);e[edges[i][1]].push_back(edges[i][0]);d[edges[i][0]];d[edges[i][1]];}for(int i0;in;i) {if(d[i]1) {q.push({i,0});res.push_back({0,i});vis[i] 1;}}while(q.size()) { //bfsint k q.front().first;int dis q.front().second;q.pop();for(int i0;ie[k].size();i) {d[e[k][i]]--;if(d[e[k][i]] 1 !vis[e[k][i]]) {q.push({e[k][i],dis1});res.push_back({dis1,e[k][i]});vis[e[k][i]] 1;}}}sort(res.begin(),res.end());ans.push_back(res[n-1].second);if(res[n-1].first res[n-2].first) ans.push_back(res[n-2].second);return ans;}
};
