前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode 333. 最大 BST 子树(递归)*

LeetCode 333. 最大 BST 子树(递归)*

作者头像
Michael阿明
发布2020-07-13 15:00:06
8610
发布2020-07-13 15:00:06
举报
文章被收录于专栏:Michael阿明学习之路

1. 题目

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

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

代码语言:javascript
复制
示例:
输入: [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?
代码语言:javascript
复制
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       3
    	if(!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

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2020/07/06 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 题目
  • 2. 解题
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档