我们可以使用递归的方法来解决这个问题。我们先定义一个函数 max_sum(node),这个函数以树的节点作为参数,返回以该节点为起点的最大路径和。然后,我们就可以在整个树中找到最大的路径和。
在 max_sum(node) 中,我们需要对每个节点的两个子节点分别调用 max_sum,找到它们的最大路径和。然后我们可以计算出以该节点为顶点的路径最大和为 node.value + max(left_sum, right_sum)。最后在所有节点调用 max_sum,找到最大的路径和即可。
下面是代码示例:
class TreeNode:
def __init__(self, value=0, left=None, right=None):
self.value = value
self.left = left
self.right = right
def max_sum(node: TreeNode) -> int:
if node is None:
return 0
left_sum = max_sum(node.left)
right_sum = max_sum(node.right)
return node.value + max(0, max(left_sum, right_sum))
def max_path_sum(root: TreeNode) -> int:
if root is None:
return 0
left_sum = max_path_sum(root.left)
right_sum = max_path_sum(root.right)
return max(max_sum(root), max(left_sum, right_sum))
给定下面的二叉树:
1
/ \
2 3
/ \
4 5
调用 max_path_sum(root) 将返回 12,对应路径为 4->2->1->3。