二叉树最大路径和：逻辑错误

Question

我正在尝试解决寻找二叉树最大路径和的问题。我将发布问题陈述。

编写一个函数，接受二叉树并返回其最大路径和。路径是树中连接的节点的集合，其中没有节点连接到两个以上的其他节点；路径和是 特定路径中节点值的总和。每个二叉树节点都有一个整数值、一个左子节点和一个右子节点。子节点可以是 二叉树节点本身或 None / null。

我需要帮助来解决这个问题。我的想法很少，但我还没有接近起草解决方案，或者逻辑无法直接转换为代码。

可能是迭代中最大路径和的答案

• 单独root
• 单独根，具有左最大路径
• 单独根，具有正确的最大路径
• 左子树中的一些双路径/三角形
• 右子树中的一些双路径/三角形

所以有两种情况：

• attachablePath（我可以添加根节点并比较其总和是否更大的路径类型）
• unattachablePath（路径类型是三角形路径，根为子树中的子节点之一）

我认为我需要一个返回两者的函数，以便调用它们的根节点可以决定 哪个对他们更有利 现在我们可能会比较并找出这两个选项

    bestAttachable = max of leftattachablePath + root, rightAttachablePath + root
    bestUnattachable = max of leftUnattachable, rightUnattachable, root, leftattachable + root + unattachable.

这有道理吗？ 请帮助我以正确的方式思考这个问题。我觉得我错过了一些可能会出错的事情。或不确定 如何有效地将逻辑转化为代码。

我试过这个

def maxPathSum(tree):
    # Write your code here.
    maxA, maxB = helper(tree)
 #   print(maxA, maxB)
    return max(maxA, maxB)
    pass


def helper(node):
    if node is None:
        return 0, float("-inf")
    left_attachable, left_unattachable = helper(node.left)
    right_attachable, right_unattachable = helper(node.right)

#    print('left is ', left_attachable, ' right is ', right_attachable)
    max_attachable = max( left_attachable+node.value, right_attachable+node.value, node.value)
    print(node.value, left_unattachable, right_unattachable, left_attachable, right_attachable)
    max_unattachable = max(left_unattachable, right_unattachable, left_attachable+node.value+right_attachable, node.value)

    return max_attachable, max_unattachable

但是在 right_attachable 或 left_attachable 为最大的情况下，这会失败。另外，我已将可连接的基本情况设置为 0 但当树具有所有负节点时，则 max 是所有节点中最小的但不是 0 但我也无法将 -inf 设置为可连接，因为当我将节点附加到它，应该是节点值的大小。

Answer 1

两者都必须保留。自下而上的方法逻辑是否节点应该知道：

• 包括其自身的最佳可连接路径 - 意味着其自身以及从左侧或右侧开始的最佳线性路径
• 当前最佳路径可连接或不可连接。

这样做的好消息是，当父节点的两个子节点都知道这些路径时，很容易计算父节点的这些路径

当你最终到达根源时，你就会得到答案......