LeetCode 第333题：最大BST子树

📖 文章摘要

本文详细解析LeetCode第333题“最大BST子树”，这是一道中等难度的二叉树问题。文章提供了自底向上的递归解法，包含C#、Python、C++三种语言实现，配有详细的算法分析和性能对比。适合想要提升二叉树和BST操作能力的程序员。

核心知识点： 二叉搜索树、递归、树的遍历、自底向上
难度等级： 中等
推荐人群： 具有基础数据结构知识，想要提升二叉树算法能力的程序员

题目描述

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

二叉搜索树（BST）的定义：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例

示例 1：

输入：
     10
    /  \
   5    15
  / \    \
 1   8    7
输出：3
解释：最大的BST子树是:
   5
  / \
 1   8

示例 2：

输入：
     4
    / \
   2   7
  / \
 2   3
输出：2

提示

给定的二叉树的大小在 [0, 10^4] 范围内。
每个节点的值在 [-10^4, 10^4] 范围内。

解题思路

方法：自底向上递归

使用自底向上的递归方法，对每个节点判断其是否构成BST。

关键点：

使用辅助类存储子树信息
自底向上传递节点信息
维护子树的最大最小值
判断BST的条件

具体步骤：

定义辅助类存储子树信息
递归处理左右子树
判断当前节点是否可以构成BST
更新最大BST子树大小
返回子树信息

时间复杂度：O(n)，其中n为节点数空间复杂度：O(h)，其中h为树的高度

图解思路

算法流程分析表

步骤	操作	状态	说明
初始化	创建辅助类	-	存储子树信息
递归左子树	获取信息	左子树状态	判断左子树是否BST
递归右子树	获取信息	右子树状态	判断右子树是否BST
合并结果	判断当前节点	更新最大值	确定是否构成更大BST

示例分析

     10
    /  \
   5    15
  / \    \
 1   8    7

处理节点5：
- 左子树：1 (BST，大小1)
- 右子树：8 (BST，大小1)
- 节点5：构成BST，大小3

处理节点15：
- 右子树：7 (BST，大小1)
- 不构成BST（7 < 15）

最终结果：3（节点5的子树）

代码实现

C# 实现

public class Solution {
    private class TreeInfo {
        public bool IsBST { get; set; }
        public int Size { get; set; }
        public int Min { get; set; }
        public int Max { get; set; }
        
        public TreeInfo(bool isBST, int size, int min, int max) {
            IsBST = isBST;
            Size = size;
            Min = min;
            Max = max;
        }
    }
    
    private int maxSize = 0;
    
    public int LargestBSTSubtree(TreeNode root) {
        if (root == null) return 0;
        LargestBSTSubtreeHelper(root);
        return maxSize;
    }
    
    private TreeInfo LargestBSTSubtreeHelper(TreeNode node) {
        if (node == null) {
            return new TreeInfo(true, 0, int.MaxValue, int.MinValue);
        }
        
        // 递归处理左右子树
        var left = LargestBSTSubtreeHelper(node.left);
        var right = LargestBSTSubtreeHelper(node.right);
        
        // 判断当前节点是否可以构成BST
        if (left.IsBST && right.IsBST && 
            node.val > left.Max && node.val < right.Min) {
            // 可以构成BST
            int size = left.Size + right.Size + 1;
            maxSize = Math.Max(maxSize, size);
            return new TreeInfo(
                true,
                size,
                Math.Min(node.val, left.Min),
                Math.Max(node.val, right.Max)
            );
        }
        
        // 不能构成BST
        return new TreeInfo(false, 0, 0, 0);
    }
}

Python 实现

class Solution:
    def largestBSTSubtree(self, root: TreeNode) -> int:
        def helper(node):
            if not node:
                return True, 0, float('inf'), float('-inf')
            
            # 递归处理左右子树
            left_is_bst, left_size, left_min, left_max = helper(node.left)
            right_is_bst, right_size, right_min, right_max = helper(node.right)
            
            # 判断当前节点是否可以构成BST
            if (left_is_bst and right_is_bst and 
                node.val > left_max and node.val < right_min):
                # 可以构成BST
                size = left_size + right_size + 1
                self.max_size = max(self.max_size, size)
                return True, size, min(node.val, left_min), max(node.val, right_max)
            
            # 不能构成BST
            return False, 0, 0, 0
        
        self.max_size = 0
        helper(root)
        return self.max_size

C++ 实现

class Solution {
    struct TreeInfo {
        bool isBST;
        int size;
        int min;
        int max;
        TreeInfo(bool b, int s, int mn, int mx) 
            : isBST(b), size(s), min(mn), max(mx) {}
    };
    
    int maxSize = 0;
    
public:
    int largestBSTSubtree(TreeNode* root) {
        if (!root) return 0;
        largestBSTSubtreeHelper(root);
        return maxSize;
    }
    
private:
    TreeInfo largestBSTSubtreeHelper(TreeNode* node) {
        if (!node) {
            return TreeInfo(true, 0, INT_MAX, INT_MIN);
        }
        
        // 递归处理左右子树
        auto left = largestBSTSubtreeHelper(node->left);
        auto right = largestBSTSubtreeHelper(node->right);
        
        // 判断当前节点是否可以构成BST
        if (left.isBST && right.isBST && 
            node->val > left.max && node->val < right.min) {
            // 可以构成BST
            int size = left.size + right.size + 1;
            maxSize = max(maxSize, size);
            return TreeInfo(
                true,
                size,
                min(node->val, left.min),
                max(node->val, right.max)
            );
        }
        
        // 不能构成BST
        return TreeInfo(false, 0, 0, 0);
    }
};

执行结果

C# 实现

执行用时：92 ms
内存消耗：38.2 MB

Python 实现

执行用时：44 ms
内存消耗：15.6 MB

C++ 实现

执行用时：8 ms
内存消耗：22.1 MB

性能对比

语言	执行用时	内存消耗	特点
C#	92 ms	38.2 MB	代码结构清晰
Python	44 ms	15.6 MB	实现最简洁
C++	8 ms	22.1 MB	性能最优

代码亮点

🎯 使用辅助类封装信息
💡 自底向上的递归设计
🔍 完整的边界条件处理
🎨 清晰的代码结构

常见错误分析

🚫 忘记处理空节点情况
🚫 BST判断条件错误
🚫 最大最小值更新错误
🚫 子树大小计算错误

解法对比

解法	时间复杂度	空间复杂度	优点	缺点
自底向上递归	O(n)	O(h)	一次遍历完成	需要额外空间
分治法	O(n)	O(h)	思路清晰	代码较复杂

📖 系列导航

🔥 算法专题合集 - 查看完整合集

📢 关注合集更新：点击上方合集链接，关注获取最新题解！目前已更新至第333题。

💬 互动交流

感谢大家耐心阅读到这里！希望这篇题解能够帮助你更好地理解和掌握这道算法题。

如果这篇文章对你有帮助，请：

👍 点个赞，让更多人看到这篇文章
📁 收藏文章，方便后续查阅复习
🔔 关注作者，获取更多高质量算法题解
💭 评论区留言，分享你的解题思路或提出疑问

你的支持是我持续分享的动力！

💡 一起进步：算法学习路上不孤单，欢迎一起交流学习！

📖 文章摘要

题目描述

示例

示例 1：

示例 2：

提示

解题思路

方法：自底向上递归

图解思路

算法流程分析表

示例分析

代码实现

C# 实现

Python 实现

C++ 实现

执行结果

C# 实现

Python 实现

C++ 实现

性能对比

代码亮点

常见错误分析

解法对比

相关题目

📖 系列导航

💬 互动交流