当前位置:网站首页>leetcode:333. 最大 BST 子树
leetcode:333. 最大 BST 子树
2022-06-10 20:55:00 【OceanStar的学习笔记】
题目来源
题目描述

题目解析
题目大概意思是:
- 给定一个二叉树,整体可能是,也可能不是二叉搜索树,但是它一定有子树是二叉搜索树,要找到节点数最多的子搜索二叉树的节点数
所以,本题需要解决两个问题:
- 找出二叉树中所有为BST的子树
- 返回最大的那个BST子树的节点数
这个最大的子搜索二叉树,有两种可能性:包含二叉树头节点,不包含二叉树头结点。
- 不包含头结点时:就需要知道左子树的最大搜索二叉树的节点数,右子树的最大搜索二叉树的节点数
- 包含头结点时:需要判断左树是不是搜索二叉树,右树是不是搜索二叉树,左树的最大值是否小于头节点,右树的最小值是否大于头节点,同时还需要左树和右树的节点数。
也就是说,root每次都需要问一问左子树和右子树:
- 最大满足二叉搜索树条件的子树有多少节点数
- 整个子树有多少节点数,整个子树的最大值、最小值是多少
- 是不是二叉搜索树
又因为,当最大搜索二叉树的节点数和节点数相等就意味着整个子树是搜索二叉树,所以可以化简为最大搜索二叉树的节点数、max、min、节点数。
所以,定义一个辅助类:
struct Info{
int maxBSTSubtreeSize;
int allSize;
int max;
int min;
explicit Info(int m, int a, int ma, int mi) {
maxBSTSubtreeSize = m;
allSize = a;
max = ma;
min = mi;
}
};
递归求解当前子树的info:
std::shared_ptr<Info> process(TreeNode *root){
if(root == nullptr){
return nullptr;
}
// 获取左右子树信息
auto leftInfo = process(root->left);
auto rightInfo = process(root->right);
// 拼凑自己的信息
int max = root->val, min = root->val, allSize = 1;
if(leftInfo != nullptr){
max = std::max(max, leftInfo->max);
min = std::min(min, leftInfo->min);
allSize += leftInfo->allSize;
}
if(rightInfo != nullptr){
max = std::max(max, rightInfo->max);
min = std::min(min, rightInfo->min);
allSize += rightInfo->allSize;
}
// [左|右]树 最大搜索二叉树大小
int p1 = -1, p2 = -1;
if(leftInfo != nullptr){
p1 = leftInfo->maxBSTSubtreeSize;
}
if(rightInfo != nullptr){
p2 = rightInfo->maxBSTSubtreeSize;
}
// 是否包含头节点
int p3 = -1;
bool leftSearch = leftInfo == nullptr || leftInfo->maxBSTSubtreeSize == leftInfo->allSize; // 左树是否是搜索二叉树
bool rightSearch = rightInfo == nullptr || rightInfo->maxBSTSubtreeSize == rightInfo->allSize; // 右树是否是搜索二叉树
if(leftSearch && rightSearch){
bool lessMaxLessX = leftInfo == nullptr || leftInfo->max < root->val; // 左树最大值是否比当前节点值小(空也认为比当前节点小)
bool rightMinMoreX = rightInfo == nullptr || rightInfo->min > root->val; // 右树最小值是否比当前节点值大(空也认为比当前节点大)
// 都满足,才能修改p3的值
if (lessMaxLessX && rightMinMoreX) {
int leftSize = leftInfo == nullptr ? 0 : leftInfo->allSize;
int rightSize = rightInfo == nullptr ? 0 : rightInfo->allSize;
p3 = leftSize + rightSize + 1;
}
}
// 最后修改,当前子树最大搜索二叉子树的大小
int maxSubSize = std::max(p1, std::max(p2, p3));
return std::make_shared<Info>(maxSubSize, max, min, allSize);
}
调用上面方法获取结果:
int maxSubSearchBinaryTreeSize(TreeNode *root){
if(root == nullptr){
return 0;
}
return process(root)->maxBSTSubtreeSize;
}
小结
二叉树递归套路总结:
- 1)假设以X节点为头,假设可以向X左树和X右树要任何信息
- 2)在上一步的假设下,讨论以X为头节点的树,得到答案的可能性(最重要)
- 3)列出所有可能性后,确定到底需要向左树和右树要什么样的信息
- 4)把左树信息和右树信息求全集,就是任何一棵子树都需要返回的信息S
- 5)递归函数都返回S,每一棵子树都这么要求
- 6)写代码,在代码中考虑如何把左树的信息和右树信息整合出整棵树的信息
边栏推荐
- Different ways to create four indexes in MySQL
- 2022-06-09 rk817 PMU battery temperature detection
- Rotate navigation bar
- If else is too easy to use? (understanding this article will further improve your logic)
- php的exec函数
- C language ---9 first knowledge of macros and pointers
- 【生成对抗网络学习 其一】经典GAN与其存在的问题和相关改进
- 数组 是否存在重复元素
- 登堂入室之soc开发环境及硬件开发准备
- Part 7: Lesson 2 general skills of consultants - how to install and uninstall SAP ERP system client
猜你喜欢

Constructing the implementation strategy of steam education for children

In 2021, the average salary will be released, and the IT industry will not be surprised

Abbexa AML1 DNA binding ELISA Kit instructions

Exec function of PHP

oc swift 混编

Course design of imitation pottery ticket of wechat applet

Install MySQL on Linux system. Problems encountered in xshell
Detailed steps and actual records of SQL server2019 installation (available for hands-on test)

Introduction to ZigBee module wireless transmission star topology networking structure

How to stimulate the vitality and driving force of cultural innovation
随机推荐
19 MySQL optimizations commonly used in projects
C use s7 Net connected to Siemens s1200plc, C # directly connected to Siemens PLC
Mysql的回表查询?如何避免?
2022-06-09 RK817 PMU 电池温度检测
How to realize the marketing purpose of small program integral mall
C程序实例1--个人通讯录管理系统
I'm doing something cool
Cordova plugin /jpush phonegap Aurora push_ Local push_ Message push
Abbkine column exkine Pro animal cell / tissue Total Protein Extraction Kit
Share some information I accumulated when I was working as a dotnet9 blog site
C#使用S7.net连接西门子S1200PLC,C#直接连接西门子PLC
Has the samesite cookie problem occurred when using identityserver?
What do software test engineers do?
Icml2022 | sharp maml: model independent meta learning for sharpness perception
解读创客空间下的教育新生态
Notes to entry: do I need to know programming for O & M?
How to view the occupied space of a table in MySQL database
SQL Server2019安装的详细步骤实战记录(亲测可用)
MySQL范围查询优化的场景实例详解
Abbexa low sample size chicken lysozyme C (Lyz) ELISA Kit