二叉树最大路径和求解：逻辑缺陷与代码优化求助

编写一个函数，输入一棵二叉树，返回其最大路径和。路径是树中相连节点的集合，每个节点最多连接两个其他节点；路径和是路径中节点值的总和。每个二叉树节点包含整数值、左子节点和右子节点，子节点可为BinaryTree节点或None/null。

我的思路 #

我梳理出可能的最大路径和情况包括：

• 仅根节点
• 根节点加左子树最大路径
• 根节点加右子树最大路径
• 左子树中的三角路径
• 右子树中的三角路径

我将路径分为两类：

• attachablePath：可附加根节点以比较更大和的路径
• unattachablePath：子树中以根的子节点为顶点的三角路径

遇到的问题 #

我尝试编写了代码，但存在两个主要问题：

1. 当左右attachablePath为最大值时会出错；
2. 当树全为负节点时，基准值设置为0会导致错误结果，若设为-inf又会影响节点附加逻辑。

尝试的代码 #

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

内容的提问来源于stack exchange，提问作者Karina