LC 0333 [M] Largest BST Subtree - ALawliet/algorithms GitHub Wiki

https://www.youtube.com/watch?v=t3kHAoRT5iQ O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def largestBSTSubtree(self, root: TreeNode) -> int:
        self.res = 0
        
        def dfs(root):
            if not root:
                return [True, float('inf'), float('-inf'), 0] # isBST, min, max, size
            
            leftIsBST, leftMin, leftMax, leftSize = dfs(root.left)
            rightIsBST, rightMin, rightMax, rightSize = dfs(root.right)
            
            if leftIsBST and rightIsBST and leftMax < root.val < rightMin:
                self.res = max(self.res, leftSize + rightSize + 1)
                return [True, min(leftMin, root.val), max(rightMax, root.val), leftSize + rightSize + 1]
            else:
                return [False, float('inf'), float('-inf'), 0]
            
        dfs(root)
        return self.res

This is definitely not O(n) solution. Please mark the complexity in the title, in order to make people not confused. For every node, you did isValid() and count() for it. This means for every node, you traverse all the nodes belong to this node, which is O(n). That is to say, you did O(n) for each node. So, when you finished the calculation, you did O(n) * n = O(n^2).

O(n^2)

class Solution:
    def largestBSTSubtree(self, root: TreeNode) -> int:    
        if not root: return 0
        
        if self.isBST(root, -inf, inf):
            return self.count(root)
        
        return max(self.largestBSTSubtree(root.left), self.largestBSTSubtree(root.right))
    
    def isBST(self, node, _min, _max):
        if not node: return True

        if not _min < node.val < _max: return False

        return self.isBST(node.left, _min, node.val) and self.isBST(node.right, node.val, _max)
    
    def count(self, node):
        if not node: return 0

        return 1 + self.count(node.left) + self.count(node.right)

O(n)

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def largestBSTSubtree(self, root: TreeNode) -> int:
        def dfs(node):
            if not node:
                return 0, inf, -inf
            
            # postorder
            l_size, l_min, l_max = dfs(node.left)
            r_size, r_min, r_max = dfs(node.right)
            
            if l_max < node.val < r_min:
                # subtrees is valid BST, we can keep counting the l and r subtree (required both subtrees are also BST)
                return l_size + r_size + 1, min(l_min, node.val), max(r_max, node.val)
            else:
                # subtrees not valid BST, just return parent the biggest from l or r subtrees
                return max(l_size, r_size), -inf, inf
        
        return dfs(root)[0]

class Solution(object):
    def largestBSTSubtree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.maxsize=0
        def dfs(node):
            if not node: return 0,float('inf'),float('-inf') # count,mmin,mmax
            lcount,lmin,lmax=dfs(node.left)
            rcount,rmin,rmax=dfs(node.right)
            
            if lcount>=0 and rcount>=0 and node.val>lmax and node.val<rmin:
                count=1+lcount+rcount
                self.maxsize=max(self.maxsize,count)
                #mmin=lmin if lmin<float('inf') else node.val
                #mmax=rmax if rmax>float('-inf') else node.val
                mmin=lmin if lcount else node.val
                mmax=rmax if rcount else node.val
                return count, mmin,mmax
            else:
                return -1,float('-inf'),float('inf')
                
        dfs(root)
        return self.maxsize

class Solution(object):
    def largestBSTSubtree(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        self.rst = 0
        self.dfs(root)
        return self.rst
        
    def dfs(self, root):
        
        if not root:
            return 0, float("inf"), float("-inf")
        
        left = self.dfs(root.left)
        right = self.dfs(root.right)
        
        if left[2] < root.val < right[1]:
            n = left[0] + right[0] + 1
        else:
            n = float("-inf")
            
        self.rst = max(self.rst, n)
        return n, min(root.val, left[1]), max(root.val, right[2])