Участник:PinkHedgehog/MSBIBT

Материал из DISCOPAL
< Участник:PinkHedgehog
Версия от 01:30, 27 мая 2020; PinkHedgehog (обсуждение | вклад) (Новая страница: «https://leetcode.com/problems/maximum-sum-bst-in-binary-tree/ <code-python> class Solution: def maxSumBST(self, root: TreeNode) -> int: def dfs(no…»)

(разн.) ← Предыдущая | Текущая версия (разн.) | Следующая → (разн.)
Перейти к: навигация, поиск

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

class Solution:
    def maxSumBST(self, root: TreeNode) -> int:    
        def dfs(node):
            if not node: return (1e9, -1e9, 0, True)
            ll, lh, ls, lv = dfs(node.left)
            rl, rh, rs, rv = dfs(node.right)
            v = lv and rv and node.val > lh and node.val < rl
            s = ls + rs + node.val if v else -1
            self.ans = max(self.ans, s)
            return (min(ll, node.val), max(rh, node.val), s, v)
        self.ans = 0
        dfs(root)
        return self.ans