描述
给定一棵树，求出这棵树的直径，即树上最远两点的距离。
包含n个结点，n-1条边的连通图称为树。
示例1的树如下图所示。其中4到5之间的路径最长，是树的直径，距离为5+2+4=11

例1
输入：
6,[[0,1],[1,5],[1,2],[2,3],[2,4]],[3,4,2,1,5]
复制
返回值：
11
复制

思路和心得：

1.同类型的题目。一个连通图，无环。找直径
解法是2次bfs
2.因为本题的边的权重不为1，是其他的整数。所以只能dfs
dfs自上而下就ok

（一）2次dfs（自上而下）

python3代码

# 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整型
#
import collections

class Solution:
    def solve(self , n , Tree_edge , Edge_value ):
        # write code here
        def get_max_dist_node(x: int, father: int, cur_dist: int):
            max_dist = cur_dist
            res_ID = x

            for y, weight in adjvex[x]:
                if y != father:
                    ID, dd = get_max_dist_node(y, x, cur_dist + weight)
                    if dd > max_dist:
                        max_dist = dd
                        res_ID = ID
            return res_ID, max_dist

        adjvex = collections.defaultdict(list)
        for i in range(n - 1):
            x = Tree_edge[i].start
            y = Tree_edge[i].end
            val = Edge_value[i]
            adjvex[x].append((y, val))
            adjvex[y].append((x, val))
        (ID1, _) = get_max_dist_node(0, -1, 0)
        (ID2, max_d) = get_max_dist_node(ID1, -1, 0)
        return max_d

c++代码

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

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

    pair<int, int> get_max_dist_node(int x, int father, int cur_dist)
    {
        int max_dist_ID = x;
        int max_dist = cur_dist;

        for (auto [y, weight] : adjvex[x])
        {
            if (y != father)
            {
                auto [ID, dd] = get_max_dist_node(y, x, cur_dist + weight);
                {
                    if (dd > max_dist)
                    {
                        max_dist = dd;
                        max_dist_ID = ID;
                    }
                }
            }
        }
        return pair<int, int>{max_dist_ID, max_dist};
    }

    int solve(int n, vector<Interval>& Tree_edge, vector<int>& Edge_value) 
    {
        // write code here
        for (int i = 0; i < n - 1; i ++)
        {
            int x = Tree_edge[i].start;
            int y = Tree_edge[i].end;
            int val = Edge_value[i];
            adjvex[x].push_back({y, val});
            adjvex[y].push_back({x, val});
        }

        auto [ID1, _] = get_max_dist_node(0, -1, 0);
        auto [ID2, max_d] = get_max_dist_node(ID1, -1, 0);
        return max_d;

    }
};

java代码

import java.util.*;

/*
 * public class Interval {
 *   int start;
 *   int end;
 * }
 */

public class Solution 
{
    /**
     * 树的直径
     * @param n int整型 树的节点个数
     * @param Tree_edge Interval类一维数组 树的边
     * @param Edge_value int整型一维数组 边的权值
     * @return int整型
     */
    public Map<Integer, List<Integer []>> adjvex = new HashMap<>();        //建图，邻接表

    public int [] get_max_dist_node(int x, int father, int cur_dist)
    {
        int max_dist_ID = x;
        int max_dist = cur_dist;

        for (Integer [] tmp1 : adjvex.getOrDefault(x, new ArrayList<>()))
        {
            int y = tmp1[0],    weight = tmp1[1];
            if (y != father)
            {
                int [] tmp2 = get_max_dist_node(y, x, cur_dist + weight);
                int ID = tmp2[0],    dd = tmp2[1];
                if (dd > max_dist)
                {
                    max_dist = dd;
                    max_dist_ID = ID;
                }
            }
        }
        return new int [] {max_dist_ID, max_dist};
    }


    public int solve (int n, Interval[] Tree_edge, int[] Edge_value) 
    {
        // write code here
        for (int i = 0; i < n - 1; i ++)
        {
            int x = Tree_edge[i].start;
            int y = Tree_edge[i].end;
            int weight = Edge_value[i];
            adjvex.putIfAbsent(x, new ArrayList<>());
            adjvex.putIfAbsent(y, new ArrayList<>());
            adjvex.get(x).add(new Integer [] {y, weight});
            adjvex.get(y).add(new Integer [] {x, weight});
        }
        int [] tmp1 = get_max_dist_node(0, -1, 0);
        int ID1 = tmp1[0];
        int [] tmp2 = get_max_dist_node(ID1, -1, 0);
        int max_d = tmp2[1];
        return max_d;
    }
}