当前位置:网站首页>返回二叉树中最大的二叉搜索子树的根节点
返回二叉树中最大的二叉搜索子树的根节点
2022-07-02 22:20:00 【明朗晨光】
1、题目
给定一棵二叉树的根节点 root,返回这棵二叉树中最大的二叉搜索子树的根节点。
2、分析
找到最大二叉搜索子树可见返回二叉树中最大的二叉搜索子树的大小,这里只是在求根节点,于是在Info
信息体中增加一个根节点的信息。
3、实现
C++版
/************************************************************************* > File Name: 039.返回二叉树最大二叉搜索子树的根节点.cpp > Author: Maureen > Mail: [email protected] > Created Time: 六 7/ 2 13:10:04 2022 ************************************************************************/
#include <iostream>
#include <vector>
#include <ctime>
using namespace std;
class TreeNode {
public:
int value;
TreeNode *left;
TreeNode *right;
TreeNode(int data) : value(data) {
}
};
//方法1
void inOrder(TreeNode *root, vector<TreeNode *> &arr) {
if (root == nullptr) return ;
inOrder(root->left, arr);
arr.push_back(root);
inOrder(root->right, arr);
}
int getBSTSize(TreeNode *root) {
if (root == nullptr) return 0;
vector<TreeNode *> arr;
inOrder(root, arr);
for (int i = 1; i < arr.size(); i++) {
if (arr[i]->value <= arr[i - 1]->value)
return 0;
}
return arr.size();
}
TreeNode *maxSubBSTRoot1(TreeNode *root) {
if (root == nullptr) return nullptr;
if (getBSTSize(root) != 0) return root;
TreeNode *leftAns = maxSubBSTRoot1(root->left);
TreeNode *rightAns = maxSubBSTRoot1(root->right);
return getBSTSize(leftAns) >= getBSTSize(rightAns) ? leftAns : rightAns;
}
//方法2
class Info {
public:
TreeNode *maxSubBSTRoot; //最大二叉搜索子树的根节点
int maxSubBSTSize; //最大二叉搜索子树的节点数
int maxVal;
int minVal;
Info(TreeNode *root, int size, int ma, int mi) :
maxSubBSTRoot(root), maxSubBSTSize(size), maxVal(ma), minVal(mi) {
}
};
Info *process(TreeNode *x) {
if (x == nullptr) {
return nullptr;
}
Info *leftInfo = process(x->left);
Info *rightInfo = process(x->right);
int maxVal = x->value;
int minVal = x->value;
int maxSubBSTSize = 0;
TreeNode *maxSubBSTRoot = nullptr;
if (leftInfo != nullptr) {
maxVal = max(maxVal, leftInfo->maxVal);
minVal = min(minVal, leftInfo->minVal);
//可能性1:最大二叉搜索子树在左树上
maxSubBSTSize = leftInfo->maxSubBSTSize;
maxSubBSTRoot = leftInfo->maxSubBSTRoot;
}
if (rightInfo != nullptr) {
maxVal = max(maxVal, rightInfo->maxVal);
minVal = min(minVal, rightInfo->minVal);
//可能性2:最大二叉搜索子树在右树上
if (rightInfo->maxSubBSTSize > maxSubBSTSize) {
maxSubBSTSize = rightInfo->maxSubBSTSize;
maxSubBSTRoot = rightInfo->maxSubBSTRoot;
}
}
//可能性3:整棵树是BST
bool leftBST = leftInfo == nullptr ? true : (leftInfo->maxSubBSTRoot == x->left && leftInfo->maxVal < x->value);
bool rightBST = rightInfo == nullptr ? true : (rightInfo->maxSubBSTRoot == x->right && rightInfo->minVal > x->value);
if (leftBST && rightBST) {
maxSubBSTRoot = x;
maxSubBSTSize = (leftInfo == nullptr ? 0 : leftInfo->maxSubBSTSize)
+ (rightInfo == nullptr ? 0 : rightInfo->maxSubBSTSize) + 1;
}
return new Info(maxSubBSTRoot, maxSubBSTSize, maxVal, minVal);
}
TreeNode *maxSubBSTRoot2(TreeNode *root) {
if (root == nullptr) return nullptr;
return process(root)->maxSubBSTRoot;
}
//for test
TreeNode *generate(int level, int maxl, int maxv) {
if (level > maxl || (rand() % 100 / (double)101) < 0.5)
return nullptr;
TreeNode *root = new TreeNode(rand() % maxv);
root->left = generate(level + 1, maxl, maxv);
root->right = generate(level + 1, maxl, maxv);
return root;
}
TreeNode *generateRandomBST(int level, int value) {
return generate(1, level, value);
}
int main() {
srand(time(0));
int maxLevel = 4;
int maxValue = 100;
int testTimes = 1000001;
cout << "Test begin:" << endl;
for (int i = 0; i < testTimes; i++) {
TreeNode *root = generateRandomBST(maxLevel, maxValue);
if (maxSubBSTRoot1(root) != maxSubBSTRoot2(root)) {
cout << "Failed!" << endl;
return 0;
}
if (i && i % 1000 == 0) cout << i << " cases passed!" << endl;
}
cout << "Success!!" << endl;
return 0;
}
Java 版
import java.util.ArrayList;
public class MaxSubBSTHead {
public static class Node {
public int value;
Node left;
Node right;
public Node(int data) {
this.value = data;
}
}
//方法一:
public static int getBSTSize(Node head) {
if (head == null) {
return 0;
}
ArrayList<Node> arr = new ArrayList<>();
in(head, arr);
for (int i = 1; i < arr.size(); i++) {
if (arr.get(i).value <= arr.get(i - 1).value) {
return 0;
}
}
return arr.size();
}
public static void in(Node head, ArrayList<Node> arr) {
if (head == null) {
return;
}
in(head.left, arr);
arr.add(head);
in(head.right, arr);
}
public static Node maxSubBSTHead1(Node head) {
if (head == null) {
return null;
}
if (getBSTSize(head) != 0) {
return head;
}
Node leftAns = maxSubBSTHead1(head.left);
Node rightAns = maxSubBSTHead1(head.right);
return getBSTSize(leftAns) >= getBSTSize(rightAns) ? leftAns : rightAns;
}
//方法二:递归套路
public static Node maxSubBSTHead2(Node head) {
if (head == null) return head;
return process(head).maxSubBSTHead;
}
public static class Info {
public Node maxSubBSTHead; //最大搜索子树的根节点
public int maxSubBSTSize;//最大搜索子树的节点数
public int max; //最大值
public int min; //最小值
public Info(Node head, int size, int ma, int mi) {
maxSubBSTHead = head;
maxSubBSTSize = size;
max = ma;
min = mi;
}
}
public static Info process(Node x) {
if (x == null) return null;
//获取左右树的信息
Info leftInfo = process(x.left);
Info rightInfo = process(x.right);
Node maxSubBSTHead = null;
int maxSubBSTSize = 0;
int max = x.value;
int min = x.value;
if (leftInfo != null) {
//左树不为空
//更新最值
max = Math.max(max, leftInfo.max);
min = Math.min(min, leftInfo.min);
//可能性1:最大搜索二叉树在左树上
maxSubBSTHead = leftInfo.maxSubBSTHead;
maxSubBSTSize = leftInfo.maxSubBSTSize;
}
if (rightInfo != null) {
max = Math.max(max, rightInfo.max);
min = Math.min(min, rightInfo.min);
//可能性2:最大搜索二叉树在右树上,前提是如果右树的最大搜索子树的size > 左树的最大搜索子树的size
if (rightInfo.maxSubBSTSize > maxSubBSTSize) {
maxSubBSTHead = rightInfo.maxSubBSTHead;
maxSubBSTSize = rightInfo.maxSubBSTSize;
}
}
//可能性3:整棵树是最大搜索二叉树
//如果左右子树的根恰好是最大搜索二叉树的根,那么X为根的二叉树就是最大搜索二叉树,x为其根
boolean leftBST = leftInfo == null ? true : (leftInfo.maxSubBSTHead == x.left && leftInfo.max < x.value);
boolean rightBST = rightInfo == null ? true : (rightInfo.maxSubBSTHead == x.right && rightInfo.min > x.value);
if (leftBST && rightBST) {
maxSubBSTHead = x;
maxSubBSTSize = (leftInfo == null ? 0 : leftInfo.maxSubBSTSize)
+ (rightInfo == null ? 0 : rightInfo.maxSubBSTSize) + 1;
}
return new Info(maxSubBSTHead, maxSubBSTSize, max, min);
}
// for test
public static Node generateRandomBST(int maxLevel, int maxValue) {
return generate(1, maxLevel, maxValue);
}
// for test
public static Node generate(int level, int maxLevel, int maxValue) {
if (level > maxLevel || Math.random() < 0.5) {
return null;
}
Node head = new Node((int) (Math.random() * maxValue));
head.left = generate(level + 1, maxLevel, maxValue);
head.right = generate(level + 1, maxLevel, maxValue);
return head;
}
public static void main(String[] args) {
int maxLevel = 4;
int maxValue = 100;
int testTimes = 1000000;
for (int i = 0; i < testTimes; i++) {
Node head = generateRandomBST(maxLevel, maxValue);
if (maxSubBSTHead1(head) != maxSubBSTHead2(head)) {
System.out.println("Oops!");
}
}
System.out.println("finish!");
}
}
边栏推荐
- Use redis to realize self increment serial number
- SharedPreferences 保存List<Bean> 到本地并解决com.google.gson.internal.LinkedTreeMap cannot be cast to异常
- Numerical solution of partial differential equations with MATLAB
- Go basic anonymous variable
- JDBC教程
- JSON数据传递参数
- [analysis of STL source code] imitation function (to be supplemented)
- LINQ usage collection in C #
- Ping domain name error unknown host, NSLOOKUP / system d-resolve can be resolved normally, how to Ping the public network address?
- PotPlayer设置最小化的快捷键
猜你喜欢
golang入门:for...range修改切片中元素的值的另类方法
RecyclerView结合ViewBinding的使用
【直播预约】数据库OBCP认证全面升级公开课
Potplayer set minimized shortcut keys
BBR 遭遇 CUBIC
Use of recyclerview with viewbinding
请求与响应
一文掌握基于深度学习的人脸表情识别开发(基于PaddlePaddle)
Data set - fault diagnosis: various data and data description of bearings of Western Reserve University
JDBC Exercise case
随机推荐
Fusion de la conversion et de la normalisation des lots
【直播预约】数据库OBCP认证全面升级公开课
Deep analysis of data storage in memory - C language
RecyclerView结合ViewBinding的使用
Call vs2015 with MATLAB to compile vs Project
万物并作,吾以观复|OceanBase 政企行业实践
[live broadcast appointment] database obcp certification comprehensive upgrade open class
BBR encounters cubic
C#中Linq用法汇集
Brief introduction to common sense of Zhongtai
[analysis of STL source code] imitation function (to be supplemented)
@How to use bindsinstance in dagger2
FOC矢量控制及BLDC控制中的端电压、相电压、线电压等概念别还傻傻分不清楚
为什么RTOS系统要使用MPU?
Makefile configuration of Hisilicon calling interface
Ideal car × Oceanbase: when the new forces of car building meet the new forces of database
JSON数据传递参数
高数有多难?AI 卷到数学圈,高数考试正确率 81%!
Arduino - character judgment function
JDBC教程