题目描述：
给定一个二叉树，找到其中最大的二叉搜索树（BST）子树，并返回该子树中节点的数量。
题目链接：
LeetCode 333. Largest BST Subtree
解题思路：
要解决这个问题，我们可以使用递归的方法来遍历整个二叉树，并在每个节点处检查以该节点为根的子树是否是一个BST。如果是BST，我们还需要知道该子树中的节点数量。为了高效地完成这个任务，我们可以在递归过程中返回一些额外的信息，具体包括：
- 当前子树是否是BST。
- 当前子树中的节点数量。
- 当前子树的最小值和最大值。
通过这些信息，我们可以在遍历过程中判断当前节点是否可以构成一个BST，并且可以合并左右子树的信息来确定以当前节点为根的子树是否是BST。
具体步骤：
-
定义一个递归函数
dfs(node)，返回一个包含四个元素的元组：- 是否是BST（布尔值）
- 子树中的节点数量（整数）
- 子树中的最小值（整数）
- 子树中的最大值（整数）
-
在递归函数中：
- 如果当前节点为空，返回
(True, 0, inf, -inf)，表示空树是BST，节点数量为0，最小值为无穷大，最大值为负无穷大。 - 递归处理左右子树，获取左右子树的信息。
- 判断当前节点是否可以构成BST：
- 当前节点值必须大于左子树的最大值且小于右子树的最小值。
- 左右子树都必须是BST。
- 如果当前节点可以构成BST，返回
(True, 左子树节点数 + 右子树节点数 + 1, min(当前节点值, 左子树最小值), max(当前节点值, 右子树最大值))。 - 如果当前节点不能构成BST，返回
(False, max(左子树节点数, 右子树节点数), -inf, inf)，表示当前子树不是BST，节点数量为左右子树中的较大值。
- 如果当前节点为空，返回
- 在主函数中调用递归函数，并返回结果中的节点数量。
代码实现：
class TreeNode:
def init(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution: def largestBSTSubtree(self, root: TreeNode) -> int: def dfs(node): if not node: return True, 0, float('inf'), float('-inf')
left_is_bst, left_size, left_min, left_max = dfs(node.left)
right_is_bst, right_size, right_min, right_max = dfs(node.right)
if left_is_bst and right_is_bst and left_max < node.val < right_min:
return True, left_size + right_size + 1, min(node.val, left_min), max(node.val, right_max)
else:
return False, max(left_size, right_size), float('-inf'), float('inf')
is_bst, size, _, _ = dfs(root)
return size示例用法
root = TreeNode(10) root.left = TreeNode(5) root.right = TreeNode(15) root.left.left = TreeNode(1) root.left.right = TreeNode(8) root.right.right = TreeNode(7)
sol = Solution() print(sol.largestBSTSubtree(root)) # 输出应为 3，因为最大的BST子树是 [10, 5, 15]
复杂度分析：
- 时间复杂度：O(N)，其中N是二叉树中的节点数。每个节点只被访问一次。
- 空间复杂度：O(H)，其中H是二叉树的高度。递归栈的深度最多为H。
通过这种方法，我们可以高效地找到最大的BST子树，并返回其节点数量。
发表回复