Python Easy Understand Solution O(n)

  • 4
    class SubTree(object):
        def __init__(self, largest, n, min, max):
            self.largest = largest  # largest BST
            self.n = n              # number of nodes in this ST
            self.min = min          # min val in this ST
            self.max = max          # max val in this ST
    class Solution(object):
        def largestBSTSubtree(self, root):
            res = self.dfs(root)
            return res.largest
        def dfs(self, root):
            if not root:
                return SubTree(0, 0, float('inf'), float('-inf'))
            left = self.dfs(root.left)
            right = self.dfs(root.right)
            if root.val > left.max and root.val < right.min:  # valid BST
                n = left.n + right.n + 1
                n = float('-inf')
            largest = max(left.largest, right.largest, n)
            return SubTree(largest, n, min(left.min, root.val), max(right.max, root.val))

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.