今天和大家聊的问题叫做 最大 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)
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
