美文网首页leetcode
leetcode 二叉树中的最大路径和 python

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

作者: DaydayHoliday | 来源:发表于2019-04-17 17:58 被阅读0次

记录一下

class Solution(object):
    def maxPathSum(self, root):
        self.max=root.val
        def maxandcontri(node):
            contri_conds=[node.val]
            max_res=node.val
            addtoright=node.val
            maxofmax_conds=[]
            if node.left:
                max_left,contri_left=maxandcontri(node.left)
                maxofmax_conds.append(max_left)
                contri_conds.append(contri_left+node.val)
                max_res=max(node.val,contri_left,contri_left+node.val)
                addtoright=max(node.val,contri_left+node.val)
            if node.right:
                max_right,contri_right=maxandcontri(node.right)
                maxofmax_conds.append(max_right)
                contri_conds.append(contri_right+node.val)
                max_res=max(max_res,contri_right,addtoright+contri_right)
            contribution=max(contri_conds)
            return max([max_res]+maxofmax_conds),contribution
        return maxandcontri(root)[0]

相关文章

网友评论

    本文标题:leetcode 二叉树中的最大路径和 python

    本文链接:https://www.haomeiwen.com/subject/brxowqtx.html