Python Easy Understand Solution O(n)


  • 4
    G
    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
            else:
                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.