从任一点出发，找到该点到达最远的点p
从点p出发找到p点到达最远的点 q
p q之间的距离即为树中最远的两个点  int point_p;
    int point_q;
    bool visit[100000];
    int Max=-1;
    int max_len=-1;
    bool first_dfs=true;//第几次调用dfs
    int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
        // write code here
        for(int i=0;i<n;i++)
            visit[i]=false;  //初始化
        dfs(Tree_edge[0].start,0,Tree_edge,Edge_value);//从任意一个点开始  找到该点所能到达的最远的点point_p
        for(int i=0;i<n;i++)
            visit[i]=false;  //初始化
        Max=-1;
        first_dfs=false;
        dfs(point_p,0,Tree_edge,Edge_value);//从point_p 找到该点所能到达的最远的点 point_q
        
        //那么point_p  到 point_q之间的距离即为  树的直径
        for(int i=0;i<n;i++)
            visit[i]=false;  //初始化
        len(point_p,point_q,0,Tree_edge,Edge_value);//获得长度
        
        return max_len;
        
        
        
        
        
        
        
    }
    
    bool len(int point1,int point2,int length,vector<Interval>& Tree_edge, vector<int>& Edge_value)
    {
        visit[point1]=true;
        if(point2==point1) //已经访问到该点
        {
            max_len=length;
            return true;
        }
         for(int i=0;i<Tree_edge.size();i++)
        {
            
            //dfs 进入未访问的节点
            if(Tree_edge[i].start==point1 && visit[Tree_edge[i].end]==false)
            {
                if(len(Tree_edge[i].end,point2,length+Edge_value[i],Tree_edge,Edge_value))
                    return true;
            }
            
            if(Tree_edge[i].end==point1 && visit[Tree_edge[i].start]==false)
            {
               if(len(Tree_edge[i].start,point2,length+Edge_value[i],Tree_edge,Edge_value))
                   return true;
            }
        }
        visit[point1]=false;

        
        return false;
    }
    
    
    
    void dfs(int point,int length, vector<Interval>& Tree_edge, vector<int>& Edge_value)
    {
        
        if(length>Max)    //每访问一个点
        {
            Max=length;
            if(first_dfs)
               point_p=point;
            else
                point_q=point;
        }
        visit[point]=true;//标记为已经访问
        for(int i=0;i<Tree_edge.size();i++)
        {
            
            //dfs 进入未访问的节点
            if(Tree_edge[i].start==point && visit[Tree_edge[i].end]==false)
                dfs(Tree_edge[i].end,length+Edge_value[i],Tree_edge,Edge_value);
            
            if(Tree_edge[i].end==point && visit[Tree_edge[i].start]==false)
                dfs(Tree_edge[i].start,length+Edge_value[i],Tree_edge,Edge_value);
        }
        visit[point]=false;

    }
    

本题需要1个注意的地方：

1. 这是无向树(没有环的无向图)，没有子节点、父节点之分，所以题目给的Tree_edge记录的边的start和end并不一定对应：比如0 -> 1 -> 2 图，可以描述为：[[0, 1], [2, 1]];所以需要重新用邻接表对图进行描述，然后利用dfs进行遍历。(图的路径就是一个节点最大两边的和，树是子树最大的两个路径的和， 树有层次)

   function solve( n ,  Tree_edge ,  Edge_value ) {
    let res = 0;
    const obj= {};
    for (let i=0; i<Tree_edge.length; ++i) {
        const v = Tree_edge[i];
        const w = Edge_value[i] || 0;
        obj[v.start] ? obj[v.start].push([w, v.end]):
                    obj[v.start] = [[w, v.end]];
        obj[v.end] ? obj[v.end].push([w, v.start]):
                    obj[v.end] = [[w, v.start]];
    }
    const dfs = (node, pre, w) => {
        let i=0;
        const arr = [];
        while(i<obj[node].length) {
            if (obj[node][i][1] !== pre) 
                arr.push(dfs(obj[node][i][1], node, obj[node][i][0]));
            ++i;
        }
        arr.push(0, 0); // 防止没有
        const one = Math.max(...arr);
        arr[arr.indexOf(one)] = -Infinity;
        const two = Math.max(...arr);
        if (one + two > res) res = one + two;
        return one + w;
    };
    dfs(Tree_edge[0].start, -1, Edge_value[0]);
    return res;
   }

/**
 * struct Interval {
 *	int start;
 *	int end;
 * };
 */

class Solution {
public:
  /**
   * 树的直径
   * @param n int整型 树的节点个数
   * @param Tree_edge Interval类vector 树的边
   * @param Edge_value int整型vector 边的权值
   * @return int整型
   */
  int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
    // build the tree
    vector<vector<pair<int, long>>> tree(n);
    for (int i = 0; i < Tree_edge.size(); ++i) { // key: 无向图要建双向边
      const auto e = Tree_edge[i];
      tree[e.start].emplace_back(e.end, Edge_value[i]);
      tree[e.end].emplace_back(e.start, Edge_value[i]);
    }

    int ans = 0;
    function<int(int, int, int)> dfs = [&](int cur, int parent, int weight) {
      int first = 0, second = 0;
      for (const auto& nei : tree[cur]) {
        if (nei.first == parent) continue;
        int len = dfs(nei.first, cur, nei.second);
        if (len > first) second = first, first = len; // 超过第一长的边，原先第一长的边就变第二长
        else if (len > second) second = len;          // 超过第二长的边，原先第一长的边还是第一长
      }
      ans = max(ans, first + second);
      return weight + first;
    };
    
    dfs(0, -1, 0);
    return ans;
  }
};

function solve( n ,  Tree_edge ,  Edge_value ) {
    const tree = buildTree(n, Tree_edge, Edge_value);
    const visited = new Array(n).fill(false);
    const {max} = dfs({tree, visited});
    return max;
}
function buildTree(n, tree_edge, edge_value) {
    const tree = new Array(n).fill(null).map(_ => []);
    for (let i = 0; i < tree_edge.length; i++) {
        const {start, end} = tree_edge[i];
        const edge_val = edge_value[i];
        tree[start].push({child: end, len: edge_val});
        tree[end].push({child: start, len: edge_val});
    }
    return tree; 
}

function dfs({tree, visited, idx = 0, max = 0}) {
    if (tree[idx].length === 0 || visited[idx]) return 0;
    visited[idx] = true;
    let m1 = 0, m2 = 0;
    for (let i = 0; i < tree[idx].length; i++) {
        const {child, len} = tree[idx][i];
        if (visited[child]) continue;
        const res = dfs({tree, visited, idx: child, max: max});
        const distance = res.maxDistance + len;
        max = res.max;
        if (distance >= m1) {
            m2 = m1;
            m1 = distance;
        } else if (distance > m2) {
            m2 = distance;
        }
    }
    max = Math.max(max, m1 + m2);
    return {maxDistance: m1, max: max};
}

DFS

参考leetcode上的1245. Tree Diameter

可以把树看作是一个没有环的无向图，使用深度优先搜素的思想遍历整棵树。由于没有环，所有不需要visit数组记录访问过的节点，只需要每次传入父节点保证子节点不会返回访问父节点。

class Edge {
    int neighbor;
    int weight;
    Edge(int neighbor, int weight) {
        this.neighbor = neighbor;
        this.weight = weight;
    }
}
public class Solution {
    private int diameter = 0;
    public int solve (int n, Interval[] Tree_edge, int[] Edge_value) {
        // 使用数组保存所有的节点
        List<Edge>[] graph = new List[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        for (int i = 0; i < Tree_edge.length; i++) {
            Interval interval = Tree_edge[i];
            int value = Edge_value[i];
            // 由于是无向图，所有每条边都是双向的
            graph[interval.start].add(new Edge(interval.end, value));
            graph[interval.end].add(new Edge(interval.start, value));
        }
        // 随机从一个节点开始dfs，这里选择的是0
        dfs(graph, 0, -1);
        return diameter;
    }
    // dfs返回值为从node节点开始的最长深度
    private int dfs(List[] graph, int node, int parent) {
        int maxDepth = 0; //从节点开始的最长深度
        int secondMaxDepth = 0; //从节点开始的第二长深度
        for (Edge edge : graph[node]) {
            int neighbor = edge.neighbor;
            if (neighbor == parent) continue; // 防止返回访问父节点
            int depth = edge.weight + dfs(graph, neighbor, node);
            if (depth > maxDepth) {
                secondMaxDepth = maxDepth;
                maxDepth = depth;
            }else if (depth > secondMaxDepth) {
                secondMaxDepth = depth;
            }
        }
        // maxDepth + secondMaxDepth为以此节点为中心的直径
        diameter = Math.max(diameter, maxDepth + secondMaxDepth);
        return maxDepth;
    }
}

# class Interval:
#     def __init__(self, a=0, b=0):
#         self.start = a
#         self.end = b

#
# 树的直径
# @param n int整型 树的节点个数
# @param Tree_edge Interval类一维数组 树的边
# @param Edge_value int整型一维数组 边的权值
# @return int整型
#
from collections import defaultdict        
class Solution:
    def solve(self , n , Tree_edge , Edge_value ):
        # write code here
        graph, table = {}, defaultdict()
        for i in range(len(Tree_edge)):
            graph.setdefault(Tree_edge[i].start, []).append(Tree_edge[i].end), graph.setdefault(Tree_edge[i].end, []).append(Tree_edge[i].start)
            table[(Tree_edge[i].start, Tree_edge[i].end)], table[(Tree_edge[i].end, Tree_edge[i].start)] = Edge_value[i], Edge_value[i]
        self.res, self.maxIndex =  0, -1
        def dfs(cnt, node, parent):
            cur = graph[node]
            for i in range(len(cur)):
                if cur[i] == parent:
                    continue
                dfs(cnt+table[(node,cur[i])], cur[i], node)
            if cnt > self.res:
                self.res = cnt
                self.maxIndex = node
        
        dfs(0, 0, -1)
        dfs(0, self.maxIndex, -1)
        return self.res
    

from collections import defaultdict
class Solution:
    def solve(self , n: int, Tree_edge: List[Interval], Edge_value: List[int]) -> int:
        def dfs(node, parent, graph):
            max_distance = 0
            max_node = node
            for neighbor, weight in graph[node]:
                if neighbor == parent:  # 避免回到父节点
                    continue
                distance, cur_max_node = dfs(neighbor, node, graph)
                distance += weight
                if distance > max_distance:
                    max_distance = distance
                    max_node = cur_max_node
            return max_distance, max_node

        graph = defaultdict(list)
        for i in range(len(Tree_edge)):
            u, v, weight = Tree_edge[i].start, Tree_edge[i].end, Edge_value[i]
            graph[u].append((v, weight))
            graph[v].append((u, weight))
        # 第一次 DFS 从任意节点开始，找到最远的节点
        start_node = Tree_edge[0].start
        _, max_node = dfs(start_node, None, graph)
        # 第二次 DFS 从找到的最远节点开始，计算直径
        max_distance, _ = dfs(max_node, None, graph)
        
        return max_distance

#include <vector>
#include <unordered_map>
#include <list>
#include <algorithm>
using namespace std;

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 树的直径
     * @param n int整型 树的节点个数
     * @param Tree_edge Interval类vector 树的边
     * @param Edge_value int整型vector 边的权值
     * @return int整型
     */
    int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) {
        // 如果边或权值数组为空，或者长度不匹配，返回0
        if (Tree_edge.empty() || Edge_value.empty() || Tree_edge.size() != Edge_value.size()) return 0;

        // 构建图的邻接表
        unordered_map<int, list<Edge>> graph;
        int len = Tree_edge.size();
        for (int i = 0; i < len; ++i) {
            int start = Tree_edge[i].start;
            int end = Tree_edge[i].end;
            int w = Edge_value[i];
            
            // 添加边 start -> end
            graph[start].emplace_back(end, w);
            // 添加边 end -> start (无向图)
            graph[end].emplace_back(start, w);
        }
        
        // 记录以节点0为起点的最长路径长度和终点
        pair<int, int> remote = {0, 0}; 
        dfs(graph, 0, -1, 0, remote);
        
        // 以远端节点为新的起点再次进行DFS，计算最长路径
        pair<int, int> result = {0, 0};
        dfs(graph, remote.second, -1, 0, result);
        
        return result.first; // 返回最长路径长度
    }

private:
    // 边的结构体，包含终点和权重
    struct Edge {
        int end;
        int weight;
        Edge(int e, int w) : end(e), weight(w) {}
    };
    
    // 深度优先搜索，用于找到最长路径
    void dfs(unordered_map<int, list<Edge>>& graph, int from, int prev, int path, pair<int, int>& res) {
        // 遍历当前节点的所有相邻边
        for (const auto& edge : graph[from]) {
            if (edge.end != prev) { // 跳过回到父节点的边
                path += edge.weight;
                
                // 更新最长路径信息
                if (path > res.first) {
                    res.first = path;
                    res.second = edge.end;
                }
                
                // 继续递归DFS
                dfs(graph, edge.end, from, path, res);
                path -= edge.weight; // 回溯，恢复路径长度
            }
        }
    }
};

import java.util.*;

/*
 * public class Interval {
 *   int start;
 *   int end;
 *   public Interval(int start, int end) {
 *     this.start = start;
 *     this.end = end;
 *   }
 * }
 */

public class Solution {
    class Edge {
        int to;
        int weight;
        public Edge(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 树的直径
     * @param n int整型 树的节点个数
     * @param Tree_edge Interval类一维数组 树的边
     * @param Edge_value int整型一维数组 边的权值
     * @return int整型
     */
    int max = Integer.MIN_VALUE;
    boolean visited[][];
    public int solve (int n, Interval[] Tree_edge, int[] Edge_value) {
        // write code here
        // 转临接表
        HashMap<Integer, ArrayList<Edge>> map = new HashMap<>();
        
        visited = new boolean[n][n];
        for(int i = 0; i < Tree_edge.length; i++) {
            Interval edge = Tree_edge[i];
            map.putIfAbsent(edge.start, new ArrayList<>());
            map.putIfAbsent(edge.end, new ArrayList<>());
            map.get(edge.start).add(new Edge(edge.end, Edge_value[i]));
            map.get(edge.end).add(new Edge(edge.start, Edge_value[i]));
        } 
        dfs(0, map);
        return max;
    }

    public int dfs(int curIndex, HashMap<Integer, ArrayList<Edge>> map) {
        int s1 = 0;
        int s2 = 0;
        List<Edge> sonList = map.get(curIndex);
        for(int i = 0; i <sonList.size(); i++) {
            int to = sonList.get(i).to;
            int weight = sonList.get(i).weight;

            if(visited[curIndex][to]) continue;
            visited[curIndex][to] = true;
            visited[to][curIndex] = true;
            int son = dfs(to, map) + weight;
            if(son > s1) {
                s2 = s1;
                s1 = son; 
            } else if(s2 < son && s1 > son) s2 = son;
        }
        max = Math.max(max, Math.max(s1, s1 + s2));
        return s1;
    }
}