Python O(n) solution


  • 0
    # Return: isBST, internal BST size, BST boundary values
    def h(r):
        if not r.left and not r.right:
            return True, 1, r.val, r.val
        if not r.left:
            check, size, low, high = h(r.right)
            if check and r.val < low:
                return True, 1 + size, r.val, high
            return False, size, None, None
        if not r.right:
            check, size, low, high = h(r.left)
            if check and r.val > high:
                return True, 1 + size, low, r.val
            return False, size, None, None
        
        Lcheck, Lsize, Llow, Lhigh = h(r.left)
        Rcheck, Rsize, Rlow, Rhigh = h(r.right)
        if Lcheck and Rcheck and Lhigh < r.val < Rlow:
            return True, 1 + Lsize + Rsize, Llow, Rhigh
        return False, max(Lsize, Rsize), None, None
    
    class Solution(object):
        def largestBSTSubtree(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            if not root:
                return 0
            return h(root)[1]
    

Log in to reply
 

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