从任一点出发，找到该点到达最远的点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
    

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

package _09_图;

import java.util.*;

public class _1245_树的直径 {
    /**
     * 无向图的最长路径
     * 6,[[0,1],[1,5],[1,2],[2,3],[2,4]],[3,4,2,1,5]
     * 11
     */

    public static void main(String[] args) {
        var test = new _1245_树的直径();
        int n = 2;
        Interval[] intervals = new Interval[n - 1];
        intervals[0] = new Interval(0, 1);

        int[] value = new int[]{2};
        System.out.println(test.solve(n, intervals, value));
    }

    int n, m;
    List<Edge>[] edges;
    boolean[] visited;
    int path = 0, vertex = -1;  //记录最大路径长度, 及终点

    public int solve(int n, Interval[] Tree_edge, int[] Edge_value) {
        // write code here
        this.n = n;
        m = Tree_edge.length;
        //邻接表存放边的数据
        edges = new List[n];
        visited = new boolean[n];
        for (int i = 0; i < n; ++i) {
            edges[i] = new ArrayList<>();
        }
        //构建无向图, 双向边
        for (int i = 0; i < m; ++i) {
            int start = Tree_edge[i].start;
            int end = Tree_edge[i].end;
            int weight = Edge_value[i];
            edges[start].add(new Edge(start, end, weight));
            edges[end].add(new Edge(end, start, weight));
        }

                //从0出发, 找到最远的顶点
        find(0, 0);
        //情况访问数组及路径长度
        Arrays.fill(visited, false);
        path = 0;
                //从该顶点出发, 再找一次, 即为最长路径
        find(vertex, 0);
        return path;
    }

    private void find(int i, int sum) {
        //标记当前顶点
        visited[i] = true;
        //判断是否需要更新路径长度
        if (sum > path) {
            path = sum;
            vertex = i;
        }
        //遍历该顶点对应的所有边
        for (Edge edge : edges[i]) {
            //如果终点访问过则跳过
            if (visited[edge.end]) {
                continue;
            }
            //标记终点
            visited[edge.end] = true;
            find(edge.end, sum + edge.weight);
            //清除终点标记
            visited[edge.end] = false;
        }
    }

    private static class Edge {
        int start;
        int end;
        int weight;

        public Edge(int start, int end, int weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        public void setStart(int start) {
            this.start = start;
        }

        public void setEnd(int end) {
            this.end = end;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }
    }

    public static class Interval {
        int start;
        int end;

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