题解 | #多叉树的直径#

/**
 * struct Interval {
 *	int start;
 *	int end;
 *	Interval(int s, int e) : start(start), end(e) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 树的直径
     * @param n int整型 树的节点个数
     * @param Tree_edge Interval类vector 树的边
     * @param Edge_value int整型vector 边的权值
     * @return int整型
     */
  // 邻接链表
    unordered_map<int,vector<pair<int,int>>> graph;
  // 访问数组，防止图遍历走回路
    vector<bool> visited;
    int res = 0;
    int target = -1;
  // 图遍历时，要记录前一个节点index，防止走回路
    void dfs(int cur, int from, int sum){
        visited[cur] = true;
        for(auto& edge : graph[cur]){
            int next = edge.first;
            int weight = edge.second;
            if(next == from || visited[next])   continue;
            dfs(next, cur, sum+weight);
        }
        if(sum > res){
            res = sum;
            target = cur;
        }
        visited[cur] = false;
        return;
    }
    int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
        int m = Tree_edge.size();
        visited.resize(n);
	  // 无向图
        for(int i=0; i<m; ++i){
            int head = Tree_edge[i].start;
            int tail = Tree_edge[i].end;
            int weight = Edge_value[i];
            graph[head].emplace_back(pair{tail, weight});
            graph[tail].emplace_back(pair{head, weight});
        }
        dfs(0,-1,0);
        dfs(target, -1, 0);
        return res;
    }
};