python - 二叉树中的最大和路径

标签 python algorithm recursion data-structures binary-tree

我正在尝试解决这个问题: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))

请注意,根节点不是 ldrd 路径的一部分。

关于python - 二叉树中的最大和路径,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/49065003/

相关文章:

python - Python 正则表达式 findall 的一些问题

递归迭代的算法分析

algorithm - 是否存在任何算法来衡量各种因素?

python - 为什么我得到这个输出? (Python)

python - 用于大型多光谱图像的 Numpy 计算 corrcoef

algorithm - Spring 和 Hook

Python:使用递归返回文件的完整路径

python - 优化python中的递归

c# - 将带有数组的 json 结构展平为多个没有数组的平面对象

python - 如何使用 python 或 pyqt 制作甘特图