Accepted 56ms Python Bottom Up Solution, O(n), beats 97%..


  • 0
    R

    I return 4 variables:
    Status (if it is a BST, True/False), nodesCount (how many nodes in the subtree), Floor(int), Ceiling(int)

    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def largestBSTSubtree(self, root):
            """
            :type root: TreeNode
            :rtype: int
            """
            self.answer = 0
            if root is None:
                return 0
            
            def helper(node):
                if node.left is None and node.right is None: 
                    self.answer = max(self.answer,1)
                    return True, 1, node.val, node.val
                
                if node.left is None and node.right: 
                    statusR, numR, rightFloor, rightCeiling = helper(node.right)
                    if statusR and node.val < rightFloor:
                        self.answer = max(self.answer, numR + 1)
                        return True, numR + 1, node.val, rightCeiling
                    else:
                        return False, 1, node.val, rightCeiling
                
                elif node.right is None and node.left:
                    statusL, numL, leftFloor, leftCeiling = helper(node.left)
                    if statusL and node.val > leftCeiling:
                        self.answer = max(self.answer, numL + 1)
                        return True, numL + 1, leftFloor, node.val
                    else:
                        return False, 1, leftFloor, node.val
                else:
                    statusL, numL, leftFloor, leftCeiling = helper(node.left)
                    statusR, numR, rightFloor, rightCeiling = helper(node.right)
    
                    if statusL and statusR and  leftCeiling < node.val < rightFloor:
                        self.answer = max(self.answer, numL + numR + 1)
                        return True, numL + numR + 1, leftCeiling, rightFloor
                    else:
                        return False, numL + numR + 1, leftCeiling, rightFloor
    
            helper(root)
            
            return self.answer
    

Log in to reply
 

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