3返回找到的最大的从上往下的max path sum + current node的值得到目前最大的path sum
class Solution:
def solve(self , n , Tree_edge , Edge_value ):
# write code here
# 1. input: Graph: n= node values, Tree_edge = list of node to node link/edge, edge_value:weight
# 2. find max path sum of any two node in tree (maximum path sum binary tree)
# idea:
# 1. build tree using dictionary
# key = node value, value = children node of key
# 2. find max path sum of any two node in tree, recursion tree, but not binary tree
# idea: max path sum of a node = max( max path sum from left tree,
# max path sum from right tree,
# max path sum from left + right + node value tree, )
# if max path sum from left/ right top-down consecutive path < 0, set it to 0
# otherwise add it to the path sum
# compare the path sum found in current node with global max
# return max top-down path sum including cur node value
#
#
# test case
if n <=1:
return None
tree = {}
self.global_max = -float('inf')
# build
for i in range(len(Tree_edge)):
if Tree_edge[i].start not in tree.keys():
tree[Tree_edge[i].start] = []
if Tree_edge[i].end not in tree.keys():
tree[Tree_edge[i].end] = []
# append children and weight to parent node's list
node, w = Tree_edge[i].end, Edge_value[i]
tree[Tree_edge[i].start].append([node,w])
# 搭建无向图，所以把 end 为key也加上去
# 加了之后为了防止有loop， 在dfs里面要家 child != parent 的条件
# 如果不加end的key到dictionary，可以不加child ！= parent的条件
tree[Tree_edge[i].end].append([Tree_edge[i].start,w])
# find max path sum
root = Tree_edge[0].start
self.findmaxsum(tree, root,-1)
return self.global_max
def findmaxsum(self, tree, node,parent):
# tree: dictionary
# node: key value in dicionary
# return max top-down path sum
if node not in tree.keys():
return 0
path_sum = 0
ret_path_sum = 0
# iterate children
path_ls = [0,0]
for i in range(len(tree[node])):
node_val = tree[node][i][0]
node_weight = tree[node][i][1]
if node_val == parent:
continue
p_sum = max(self.findmaxsum(tree, node_val,node)+node_weight, 0)
ret_path_sum = max(ret_path_sum, p_sum)
# compute path sum across two branches
if p_sum > path_ls[0]:
if p_sum > path_ls[1]:
path_ls[0] = path_ls[1]
path_ls[1] = p_sum
else:
path_ls[0] = p_sum
path_sum = sum(path_ls)
# update global max
self.global_max = max(self.global_max, path_sum)
return path_ls[1]