LeetCode 333. 最大 BST 子树（递归）*

文章目录

• • 1. 题目
  • 2. 解题

1. 题目

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

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

示例: 输入: [10,5,15,1,8,null,7]10 / \ 5 15 / \ \ 1 8 7 输出: 3 解释: 高亮部分为最大的 BST 子树。（1，5，8）返回值 3 在这个样例中为子树大小。 进阶: 你能想出用 O(n) 的时间复杂度解决这个问题吗？

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/largest-bst-subtree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

• 自底向上dfs，返回值 子树 min, max, node个数, 是bst？

class Solution {int maxNode = 1; public:int largestBSTSubtree(TreeNode* root) {if(!root) return 0;dfs(root);return maxNode;}vector<int> dfs(TreeNode* root)//返回子树min,max,node个数,是bst？{ // 0 1 2 3if(!root) return {INT_MAX,INT_MIN,0,1};auto l = dfs(root->left);auto r = dfs(root->right);bool bst = (l[3] && r[3] && l[1] < root->val && root->val < r[0]);int node = l[2]+r[2]+1;int MAX = !root->right ? root->val : r[1],MIN = !root->left ? root->val : l[0];if(bst)maxNode = max(maxNode, node);return {MIN,MAX,node,bst};} };

20 ms 30.8 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

长按或扫码关注我的公众号（Michael阿明），一起加油、一起学习进步！

总结

以上是生活随笔为你收集整理的LeetCode 333. 最大 BST 子树（递归）*的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。