Участник:Ковальков Антон М05-903б/Binary Tree Maximum Path Sum

Материал из DISCOPAL
Перейти к: навигация, поиск

https://leetcode.com/problems/binary-tree-maximum-path-sum

Python3

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxPathSum(self, root: TreeNode) -> int:
        def go(node: TreeNode):
            if node is None:
                return -float('inf'), 0
            l_max, l_longest = go(node.left)
            r_max, r_longest = go(node.right)
            a = node.val
            if l_longest > 0:
                a += l_longest
            if r_longest > 0:
                a += r_longest
            return (
                max(l_max, r_max, a),
                max(l_longest, r_longest, 0) + node.val
            )
        return go(root)[0]