我正在尝试解决这个问题:https://leetcode.com/problems/binary-tree-maximum-path-sum/description/ .
寻找最大和路径就像寻找任意两个节点之间的最大路径,该路径可能会也可能不会通过根;除了最大总和路径,我们想要跟踪总和而不是路径长度。
因此,我调整了二叉树解的直径来找到最大和路径。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def height(self, root):
if root==None:
return 0
lh = self.height(root.left)
rh = self.height(root.right)
return max(root.val+lh, root.val+rh)
def maxPathSum(self, root):
"""
:type root: TreeNode
:rtype: int
"""
if root==None:
return 0
lh = self.height(root.left)
rh = self.height(root.right)
ld = self.maxPathSum(root.left)
rd = self.maxPathSum(root.right)
return max(lh+rh+root.val, root.val+ max(ld , rd))
我的解决方案是在失败之前通过 40 个测试用例。
我一直在试图找出正确的解决方案。我的解决方案适用于查找直径,我只是在返回值中添加了总和。
为什么这不是一个通用的解决方案,因为我清楚地遍历了所有路径并在返回值中获取适当的最大值。
感谢您的帮助。
最佳答案
问题出在这一行
return max(lh+rh+root.val, root.val+ max(ld , rd))
应该是
return max(lh+rh+root.val, max(ld , rd))
请注意,根节点不是 ld
和 rd
路径的一部分。
关于python - 二叉树中的最大和路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49065003/