Straightforward Python O(n) solution


  • 0

    In a BST, a root node is greater than any node in left sub-tree and less than any node in right sub-tree. Thus, when backtracking, we need three variables to store the information of empty or illegal BST and MAX, MIN value of this sub-tree.

    class Solution(object):
        def largestBSTSubtree(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            def dfs(root):
                if not root:
                    return (-1, -1, -1) # status, min, max
                if not root.left and not root.right:
                    return (1, root.val, root.val)
                
                median = root.val
                left = dfs(root.left)
                right = dfs(root.right)
                if left[0] > 0 and right[0] > 0 and median > left[2] and median < right[1]:
                    self.maxBST = max(self.maxBST, left[0] + right[0] + 1)
                    return (left[0] + right[0] + 1, left[1], right[2])
    
                if left[0] == -1 and right[0] > 0 and median < right[1]:
                    self.maxBST = max(self.maxBST, right[0] + 1)
                    return (right[0] + 1, median, right[2])
                    
                if left[0] > 0 and right[0] == -1 and median > left[2]:
                    self.maxBST = max(self.maxBST, left[0] + 1)
                    return (left[0] + 1, left[1], median)
                return (0, -1, -1)
    
            if not root:
                return 0
            self.maxBST = 1
            dfs(root)
            return self.maxBST
    

Log in to reply
 

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