public class test21 {
// 定义一个内部类Node，表示二叉树的节点
public static class Node {
public int value; // 节点的值
public Node left; // 左子节点
public Node right; // 右子节点
// 构造函数，初始化节点的值
public Node(int data) {
this.value = data;
}
}
//1.与x无关，找左树最大二叉搜索子树大小和右树最大二叉搜索子树大小 //2.与x有关，左树得整体是搜索二叉树，右树得整体是搜索二叉树，左树的max要小于x的值，右树的min要大于x的值
// 定义一个内部类Info，用于存储关于二叉树的信息
public static class Info {
public boolean isAllBST; // 是否为搜索二叉树
public int maxSubBSTSIZE; // 最大子树的大小
public int min; // 整棵树的最小值
public int max; // 整棵树的最大值
// 构造函数，初始化Info对象的属性
public Info(boolean is, int size, int mi, int ma) {
isAllBST = is;
maxSubBSTSIZE = size;
min = mi;
max = ma;
}
}
// process方法，返回给定节点X的二叉树信息
public static Info process(Node X){
if(X == null){
return null; // 如果节点为空，返回null
}
// 递归处理左子树和右子树
Info leftInfo = process(X.left);
Info rightInfo = process(X.right);
// 初始化当前节点的最小值和最大值为节点的值
int min = X.value;
int max = X.value;
// 如果左子树信息不为空，更新最小值和最大值
if(leftInfo != null){
min = Math.min(min , leftInfo.min);
max = Math.max(max , leftInfo.max);
}
// 如果右子树信息不为空，更新最小值和最大值
if(rightInfo != null){
min = Math.min(min , rightInfo.min);
max = Math.max(max , rightInfo.max);
}
// 初始化最大子树大小为0
int maxSubBSTSIZE = 0;
// 如果左子树信息不为空，更新最大子树大小
if(leftInfo != null){
maxSubBSTSIZE = leftInfo.maxSubBSTSIZE;
}
// 如果右子树信息不为空，更新最大子树大小
if(rightInfo != null){
maxSubBSTSIZE = Math.max(maxSubBSTSIZE , rightInfo.maxSubBSTSIZE);
}
// 初始化isAllBST为false
boolean isAllBST = false;
// 判断当前节点是否满足搜索二叉树的条件
if( //左侧整体需要是搜索二叉树的条件
//右侧整体需要是搜索二叉树的条件
//左侧最大值<X
//右侧最小值>X
(leftInfo == null ? true : leftInfo.isAllBST)
&& (rightInfo == null ? true : rightInfo.isAllBST)
&&(leftInfo ==null ? true : leftInfo.max < X.value)
&&(rightInfo ==null ?true : rightInfo.min >X.value)
){
// 如果满足条件，更新最大子树大小和isAllBST标志
maxSubBSTSIZE =
(leftInfo ==null ? 0 : leftInfo.maxSubBSTSIZE)
+
(rightInfo ==null ? 0 : rightInfo.maxSubBSTSIZE)
+
1;
isAllBST = true;
}
// 返回当前节点的二叉树信息
return new Info(isAllBST , maxSubBSTSIZE , min , max);
}
}
