题解 | #多叉树的直径#

思路：

对于任意节点，计算最远节点距离和第二远节点距离，两距离之和是通过当前节点的最远路径。

直径即通过每个节点的最远路径的最大值。

使用递归方法遍历整个树，在递归函数中同时完成距离的计算与通过当前节点最远路径的计算和比较

# 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整型
#
class Solution:
    def solve(self , n: int, Tree_edge: List[Interval], Edge_value: List[int]) -> int:
        if len(Tree_edge) == 0:
            return 0
        if len(Tree_edge) <= 2:
            return sum(Edge_value)

        # Dictionary for ease of traverse
        edge_dict = dict()
        for edge, value in zip(Tree_edge, Edge_value):
            print(edge.start, edge.end, value)
            start = edge.start
            end = edge.end
            if start in edge_dict:
                edge_dict[start].append((end, value))
            else:
                edge_dict[start] = [(end, value)]
            if end in edge_dict:
                edge_dict[end].append((start, value))
            else:
                edge_dict[end] = [(start, value)]

        def diameter(path:List[int]):
            node_i = path[-1]
            top_distance = 0 # 最长距离
            sec_distance = 0 # 第二长距离
            temp_diameter = 0 # 通过各节点最远路径距离的最大值
            for next_node, edge_length in edge_dict[node_i]:
                if next_node in path:
                    continue
                distance, ret_diameter = diameter(path + [next_node])
                distance = distance + edge_length
                temp_diameter = max(temp_diameter, ret_diameter)
                if distance > top_distance:
                    sec_distance = top_distance
                    top_distance = distance
                elif distance > sec_distance:
                    sec_distance = distance
                # print(node_i, next_node, edge_length, distance, temp_diameter)
            temp_diameter = max(temp_diameter, top_distance + sec_distance)
            print(node_i, top_distance, temp_diameter)
            return (top_distance, temp_diameter)

        # 从任意节点开始
        any_node = Tree_edge[0].start
        return diameter([any_node])[1]