描述：递归调用，getMax返回 [节点值，经过节点左子节点的最大值，经过节点右节点的最大值]，每次递归同时查看是否存在不经过节点的值大于max。
代码：待优化
def getLargeNode(self, a, b):
if a and b:
return max(a, b)
elif a and not b:
return a
elif not a and b:
return b
else:
tmp = None def getMax(self, node):
if node is None:
return [None, None, None] left = self.getMax(node.left)
right = self.getMax(node.right) pass_node_max = node.val
if left[0] is not None:
if left[1] > self.maxPath:
self.maxPath = item
if left[2] > self.maxPath:
self.maxPath = item tmp = self.getLargeNode(left[1], left[2]) if tmp is not None:
if tmp <= 0 and left[0] <= 0:
left_val = left[0]
elif tmp > 0 and left[0] <= 0:
left_val = left[0] + tmp
if tmp + left[0] > 0:
pass_node_max += left_val
elif tmp <= 0 and left[0] > 0:
left_val = left[0]
pass_node_max += left_val
else:
left_val = left[0] + tmp
pass_node_max += left_val
else:
left_val = left[0]
if left[0] > 0:
pass_node_max += left[0]
else:
left_val = None if right[0] is not None:
if right[1] > self.maxPath:
self.maxPath = right[1]
if right[2] > self.maxPath:
self.maxPath = right[1] tmp = self.getLargeNode(right[1], right[2]) if tmp is not None:
if tmp <= 0 and right[0] <= 0:
right_val = right[0]
elif tmp > 0 and right[0] <= 0:
right_val = right[0] + tmp
if tmp + right[0] > 0:
pass_node_max += right_val
elif tmp <= 0 and right[0] > 0:
right_val = right[0]
pass_node_max += right_val
else:
right_val = right[0] + tmp
pass_node_max += right_val
else:
right_val = right[0]
if right[0] > 0:
pass_node_max += right[0]
else:
right_val = None if pass_node_max > self.maxPath:
self.maxPath = pass_node_max return [node.val, left_val, right_val] def maxPathSum(self, root):
self.maxPath = root.val
if not(root.left or root.right):
return self.maxPath result = self.getMax(root) root_val = root.val
if result[1] > 0:
root_val += result[1]
if result[2] > 0:
root_val += result[2]
if root_val > self.maxPath:
self.maxPath = root_val if result[1] > self.maxPath:
self.maxPath = result[1]
if result[2] > self.maxPath:
self.maxPath = result[2] return self.maxPath