LeetCode刷题实战333：最大 BST 子树-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 最大 BST 子树，我们先来看题面：

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

Given a binary tree, find the largest subtree which is a Binary Search Tree (BST), where largest means subtree with largest number of nodes in it.
Note: A subtree must include all of its descendants.

给定一个二叉树，找到其中最大的二叉搜索树（BST）子树，其中最大指的是子树节点数最多的。

注意:

子树必须包含其所有后代。

示例

示例:

输入: [10,5,15,1,8,null,7]

   10
   / \
  5  15
/ \ \
1   8   7

输出: 3
解释: 高亮部分为最大的 BST 子树。
     返回值 3 在这个样例中为子树大小。

解题

思路一：判断每个节点是否是二叉搜索树

class Solution:
    def largestBSTSubtree(self, root: TreeNode) -> int:

        self.res = 0
        def isValid(root, t1, t2):
            if not root:
                return 0
            if root.val >= t2 or root.val <= t1:
                return float("-inf")
            return 1 + isValid(root.left, t1, root.val) + isValid(root.right, root.val, t2)

        def helper(root):
            if not root:
                return 
            self.res = max(self.res, isValid(root,float("-inf"), float("inf")) )
            helper(root.left)
            helper(root.right)