333. Largest BST SubtreeUntitled

333. Largest BST Subtree

https://leetcode.com/problems/largest-bst-subtree/leetcode.com

粗暴点就是递归验证每个node下面是不是BST，利用BST的特性，传递val的大小限制即可。

要求O(n)解决问题，就只能：

1. 遍历常数次 -> 减少不必要的重复搜索 ->

2. 从叶节点开始检查 -> recursively

3. 往上传递val大小限制

4. 发现当前node不符合BST，就把当前size归零，继续遍历

5. 随时记录得到的最大size

# 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 __init__(self):
        # 记录最大的 subtree size
        self.maxSize = 0
        
    def explore(self, subRoot):
        # 到叶节点再往下就停住，返回一个不可能大于的min，和一个不可能小于的max.
        if subRoot == None:
            return (0, float('inf'), float('-inf'))
        # 得到两个 subtree 各自的size和val大小限制
        leftSize, leftMin, leftMax = self.explore(subRoot.left)
        rightSize, rightMin, rightMax = self.explore(subRoot.right)
        #print("--------")
        #print("[SubRoot]:", subRoot.val)
        #print("leftMax:", leftMax, "| rightMin", rightMin)
        #print("--------")
        # 如果当前节点仍然可以是 subtree 的一部分：
        if (subRoot.val > leftMax) and (subRoot.val < rightMin):
            # 计算继承的 subtree size
            inheritSize = leftSize+rightSize+1
            # 更新最大size
            self.maxSize = max(self.maxSize, inheritSize)
            return (inheritSize, min(leftMin, rightMin, subRoot.val), max(leftMax, rightMax, subRoot.val))
        # 如果当前节点断开了 BST subtree, size归零，同时返回一定可以继续的大小限制
        else:
            return (0, float('-inf'), float('inf'))
        
    def largestBSTSubtree(self, root: TreeNode) -> int:
        self.explore(root)
        return self.maxSize