Python 8 lines simple solution

  • 0
    def largestBSTSubtree(self, root):
        :type root: TreeNode
        :rtype: int
        return self.dfs(root)[2]
    def dfs(self, root):
        # return isBST(boolean), range, count
        if not root:
            return True, (float('inf'), -float('inf')), 0
        left_bst, left_range, left_count = self.dfs(root.left)
        right_bst, right_range, right_count = self.dfs(root.right)
        if left_bst and right_bst and left_range[1] < root.val < right_range[0]:
                return True, (min(left_range[0], root.val), max(right_range[1], root.val)), left_count+right_count + 1
        return False, None, max(left_count, right_count)

Log in to reply

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