我正在try 解决一个寻找二叉树最大路径和的问题.我会张贴问题陈述.
写一个函数，接受一个二叉树并返回它的最大路径和.路径是树中连接 node 的集合，其中没有 node 连接到两个以上的其他 node ;路径和是 一个特定路径中 node 的值的总和.每个BinaryTree node 都有一个整数值，一个左子 node 和一个右子 node .子 node 可以是 BinaryTree node 本身或None / null.
我需要帮助来解决这个问题.我没有什么 idea ，但我还没有接近于起草解决方案，或者逻辑没有直接转换为代码.
在迭代中可能是最大路径和的答案
- 单独的根
- 单独的根 with a left max path
- 单独的根 with a right max path
- 左子树中的一些双路径/三角形
- 右子树中的某些双路径/三角形
因此，有两种情况:
- attachablePath(可以添加根 node 并比较其和是否更大的路径类型)
- unattachablePath(以根作为子树中的子级之一的三角形路径的路径类型)
我想我需要一个函数来返回这两者，这样调用它们的根 node 就可以决定 哪个对他们更有利 现在我们可能会比较并弄清楚这两种 Select
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_attacable或Left_attacable为最大值的情况下，此操作会失败.此外，我已经将attacable的基本情况设置为0，但当树具有所有负 node 时，max是所有 node 中最小的，但不是0，但我不能将-inf也设置为attacable，因为当我将 node 附加到它时，它应该是 node 值的大小.