This problem could be solved by using DFS (inorder traversal) with some additional variables.
The basic theory of this problem is that, for every node in a Binary Search Tree, nodes in its left sub-tree is less than the node, and node i its right sub-tree is greater than its left sub-tree. And we would use this theory and DFS to solve this problem.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def largestBSTSubtree(self, root: TreeNode) -> int:
if root is None:
return 0
return self._helper(root)['size']
def _helper(self, node):
"""
:return: [min, max, is_bst, size]
"""
is_bst = True
if node.left is None:
l = {
'min': node.val,
'max': node.val,
'is_bst': True,
'size': 0
}
else:
l = self._helper(node.left)
is_bst = is_bst and l['is_bst'] and l['max'] < node.val
if node.right is None:
r = {
'min': node.val,
'max': node.val,
'is_bst': True,
'size': 0
}
else:
r = self._helper(node.right)
is_bst = is_bst and r['is_bst'] and r['min'] > node.val
if not is_bst:
return {
'min': 0,
'max': 0,
'is_bst': False,
'size': max(l['size'], r['size'])
}
return {
'min': l['min'],
'max': r['max'],
'is_bst': True,
'size': l['size'] + r['size'] + 1
}