Short Python solution


  • 24
    def largestBSTSubtree(self, root):
        def dfs(root):
            if not root:
                return 0, 0, float('inf'), float('-inf')
            N1, n1, min1, max1 = dfs(root.left)
            N2, n2, min2, max2 = dfs(root.right)
            n = n1 + 1 + n2 if max1 < root.val < min2 else float('-inf')
            return max(N1, N2, n), n, min(min1, root.val), max(max2, root.val)
        return dfs(root)[0]
    

    My dfs returns four values:

    • N is the size of the largest BST in the tree.
    • If the tree is a BST, then n is the number of nodes, otherwise it's -infinity.
    • If the tree is a BST, then min and max are the minimum/maximum value in the tree.

  • 0
    E

    smart to set n to -infinity when it's not BST! all the parents node will have size -infinity too, so no need to add another attribute for isBST


  • 0

    Wow, this -inf trick saves a lot of comparison.


  • 2

    Mine is very similar to yours:

    class Solution(object):
        def largestBSTSubtree(self, root):
            def solve(root, maxval):
                if not root: return 0, float('inf'), -float('inf')
                left,  minvl, maxvl = solve(root.left, maxval)
                right, minvr, maxvr = solve(root.right, maxval)
                if left == -1 or right == -1 or not maxvl < root.val < minvr:
                    return -1, 0, 0
                maxval[0] = max(maxval[0], 1 + left + right)
                return 1 + left + right, min(root.val, minvl, minvr), max(root.val, maxvr, maxvl)
            
            maxval = [0]
            solve(root, maxval)
            return maxval[0]
    
            # 71 / 71 test cases passed.
    	# Status: Accepted
            # Runtime: 100 ms
    
    
    

  • 0
    C

    smart solution !


  • 0
    S

    Below gave faster run time , probably because it terminates as soon as it finds a largest BST - even though asymptotic complexity is not O(n). Worst case performance is likely only when its there're no BST greater than size 1 (leaf)

    class Solution(object):
        def largestBSTSubtree(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            def isbst(root, minv, maxv):
                if root:
                    return minv < root.val < maxv and isbst(root.left, minv, root.val) and isbst(root.right, root.val, maxv)
                return True
            
            def size(root):
                if root:
                    return size(root.left) + size(root.right) + 1
                return 0
            
            if not root:
                return 0
        
            sentinel = TreeNode(None)
            q    = []
            ans  = 0
            q.append(root)
            q.append(sentinel)
            while q:
                node = q.pop(0)
                if node is sentinel:
                    if ans > 1:
                        return ans
                    if q:
                        q.append(sentinel)
                    continue
                    
                if isbst(node, -float('inf'), float('inf')):
                    #print('isbst', node.val)
                    ans = max(ans,size(node))
                if node.left:
                    q.append(node.left)
                if node.right:
                    q.append(node.right)
            return ans
    

    Also inspired by this code, I wrote following, which led to double the run time - looks like namedtuple incur overhead

    class Solution(object):
        def largestBSTSubtree(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
    
            self.ans = 0
            Result = collections.namedtuple('Result', ['isBst', 'size', 'minv', 'maxv'])
    
            def func(root, minv, maxv):
                if root:
                    left = func(root.left, minv, root.val)
                    right = func(root.right, root.val, maxv)
                    isBst = left.isBst and right.isBst and left.maxv < root.val < right.minv
                    size = 0
                    if left.isBst:
                        self.ans = max(self.ans, left.size)
                    if right.isBst:
                        self.ans = max(self.ans, right.size)
                    if isBst:
                        size = left.size + 1 + right.size
                        self.ans = max(self.ans, size)
                    minv = min(left.minv, root.val)
                    maxv = max(right.maxv, root.val)
                    return Result(isBst, size, minv, maxv)
    
                return Result(isBst=True, size=0, minv=float('inf'), maxv=-float('inf'))
    
            func(root, -float('inf'), float('inf'))
            return self.ans
    

  • 0

    @sha256pki said in Short Python solution:

    Below gave faster run time

    Such statements are useless. Because almost always, people don't measure properly. So such statements can't be trusted. How much faster, and how consistently? How often did you submit each? What were the individual times? What were the average times?


Log in to reply
 

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