题解 | #树的直径#

本题最大的麻烦之处在于输入是离散的一条条边，没有直接保存节点，需要从这些边当中提取节点的信息，从而将他们处理成树的关系，即：要保存节点，以及节点之间的边长

由于不是二叉树，每个节点的子节点可能存在多个，则需要用一个二维的结构来保存树。

然后再使用“二叉树中的最大路径和”的结题思路，采取动态规划算法即可。

这里我是用了字典结构，键是起始节点，值是终止节点，遍历一次可以得到每个节点到其他节点的关系。为了避免输入有向性造成树的构建不完整，因此每个节点都单独保存，在递归计算的时候把上级节点序号传入，用来避免原路返回，以题中的样例，即：

{
	0:[1],
	1:[0,2,5],
	2:[1,3,4],
    3:[2],
    4:[2],
    5:[1]
}

空间复杂度是O(2n-2)=>O(n),时间复杂度是遍历全树的时间O(n),具体代码如下：

global maxlen,graph,graph_value
maxlen=float('-inf')
def walk(startnode,prenode):
    global maxlen,graph,graph_value
    if len(graph[startnode])==1 and graph[startnode][0]==prenode:
        return float('-inf')#1.只是求最大路径和，则端点返回最大路径是负无穷
        #return 0#2. 如果是必须经过，则端点返回最大路径0

    singleMax=[]#保存不同下级节点经过本级节点时最大路径
    for i in range(len(graph[startnode])):
        endnode=graph[startnode][i]
        if endnode==prenode:#忽略上级来的节点，只往下走
            continue
        maxtmp=max(graph_value[startnode][i]+walk(endnode,startnode),graph_value[startnode][i])#1.只是求最大路径和，可以不要下级的数据
        #maxtmp=graph_value[startnode][i]+walk(endnode,startnode)#2. 如果是必须经过，则不能不要下级节点的数据
        singleMax.append(maxtmp)
    singleMax.sort(reverse=True)
    if len(singleMax)==1:#只有一个下级节点时
        maxlen=max(maxlen,singleMax[0])
    elif len(singleMax)>1:#多个下级节点时，最大的两边组成最长路径
        maxlen=max(maxlen,singleMax[0]+singleMax[1])
    return singleMax[0]#向上返回过当前节点的最大路径
                
class Solution:
    def solve(self , n: int, Tree_edge: List[Interval], Edge_value: List[int]) -> int:
        # write code here
        global maxlen,graph,graph_value
        if n<=1:
            return 0
        if n==2:
            return Edge_value[0]
        else:
            graph={}
            graph_value={}
            for i in range(len(Tree_edge)):#保存每个节点到其他节点的边，以及边长
                edge=Tree_edge[i]
                if edge.start not in graph:
                    graph[edge.start]=[]
                    graph_value[edge.start]=[]
                if edge.end not in graph:
                    graph[edge.end]=[]
                    graph_value[edge.end]=[]
                graph[edge.start].append(edge.end)
                graph[edge.end].append(edge.start)
                graph_value[edge.start].append(Edge_value[i])
                graph_value[edge.end].append(Edge_value[i])
        
        for startnode in graph:
            if len(graph[startnode])==1:#取一个末端端点作为起点,或者随意找一个点均可
                break

        global maxlen
        walk(startnode,'-1')#初始节点没有上级节点
        return maxlen