题解 | #多叉树的直径#

多叉树的直径

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;
    }
};