题解 | #多叉树的直径#
多叉树的直径
https://www.nowcoder.com/practice/a77b4f3d84bf4a7891519ffee9376df3
题目不难，多叉树的后序遍历
难点在于输入给的是边的形式，两个相邻点（没有区分父亲和孩子）还有对应边的权值
所以第一步就是将输入转化为无向图（邻接表形式）
第二步找到任意一个入度为0的顶点，即树的根。
第三步图的深度优先遍历。struct edge{
int value;
int nextp;
edge():value(0),nextp(0){};
edge(int n,int v):value(v),nextp(n){}
};
class Solution {
public:
/**
* 树的直径
* @param n int整型 树的节点个数
* @param Tree_edge Interval类vector 树的边
* @param Edge_value int整型vector 边的权值
* @return int整型
*/
int dis(map<int ,vector<edge>> &graph,int &res,int root,map<int,int> &visit){
int tempmax1=0,tempmax2=0;
visit[root]=1;
if(graph[root].size()==0)
return 0;
for(int i=0;i<graph[root].size();++i){
if(visit[graph[root][i].nextp]==1)
continue;
int tempmax=dis(graph,res,graph[root][i].nextp,visit)+graph[root][i].value;
if(tempmax>tempmax1){
tempmax2=tempmax1;
tempmax1=tempmax;
}
else if(tempmax>tempmax2)
tempmax2=tempmax;
}
res=max(res,tempmax1+tempmax2);
return max(tempmax1,tempmax2);
}
int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
// write code here
map<int,vector<edge>> graph; //邻接表
map<int,int> roots;
map<int,int> visits;
for(int i=0;i<Tree_edge.size();++i){
//统计顶点出现次数（仅出现一次的就是入度为0的顶点）
++roots[Tree_edge[i].start];
++roots[Tree_edge[i].end];
//建立无向图
graph[Tree_edge[i].start].push_back({Tree_edge[i].end,Edge_value[i]});
graph[Tree_edge[i].end].push_back({Tree_edge[i].start,Edge_value[i]});
visits[Tree_edge[i].start]=0;
visits[Tree_edge[i].end]=0;
}
int root=0;
//找一个根
for(auto i:roots)
if(i.second==1){
root=i.first;
break;
}
int res=0;
dis(graph,res,root,visits);
return res;
}
};
