返回二叉树中最大的二叉搜索子树的大小

1、题目

给定一棵二叉树的根节点 root，返回这棵二叉树中最大的二叉搜索子树的大小

2、分析

一棵二叉树可能它不是二叉搜索树，但是它的子树可能是二叉搜索树。

使用二叉树的递归套路。

①目标：求 X 为根节点的二叉树的最大二叉搜索子树的节点数。

②可能性：

1）X 不做根的情况：
（1）结果在左树上，左树上的maxBSTSubTreeSize；
（2）结果在右树上，右树上的maxBSTSubTreeSize;

2）X 做根的情况。那么整棵树都是BST，需要证明该树是BST，则需要向左右树获取的信息：（1）左树是不是BST；
（2）右树是不是BST；
（3）左树的max < x；
（4）右树的min > x；
（5）左树的size + 右树的size + 1。

整理所有条件的并集可得需要的信息：
（1）maxBSTSubTreeSize;
（2）是否为BST
（3）max
（4）min
（5）size
但是可以化简，如果maxBSTSubTreeSize 和 size 是相等的，那么整棵树就是BST，所以（2）这个信息可以不要。

3、实现

C++ 版

//暂未提交验证
/************************************************************************* > File Name: 038.返回二叉树最大二叉搜索子树的大小.cpp > Author: Maureen > Mail: [email protected] > Created Time: 六 7/ 2 12:47:20 2022 ************************************************************************/

#include <iostream>
using namespace std;

class TreeNode {
    
public:
    int value;
    TreeNode *left;
    TreeNode *right;

    TreeNode(int data) : value(data) {
    }
};

class Info {
    
public:
    int maxBSTSubTreeSize;//最大搜索二叉树的节点数
    int maxVal; //树的最大值
    int minVal; //树的最小值
    int allSize; //树的节点数

    Info(int mbs, int ma, int mi, int all) : 
        maxBSTSubTreeSize(mbs), maxVal(ma), minVal(mi), allSize(all) {
    }
};

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 allSize = 1;
    int p1 = -1;
    int p2 = -1;
    int p3 = -1;
    if (leftInfo != nullptr) {
    
        maxVal = max(maxVal, leftInfo->maxVal);
        minVal = min(minVal, leftInfo->minVal);
        allSize += leftInfo->allSize;
        //可能性1：答案在左树
        p1 = leftInfo->maxBSTSubTreeSize;
    }

    if (rightInfo != nullptr) {
    
        maxVal = max(maxVal, rightInfo->maxVal);
        minVal = min(minVal, rightInfo->minVal);
        allSize += rightInfo->allSize;
        //可能性2：答案在右树
        p2 = rightInfo->maxBSTSubTreeSize;
    }
    
    //可能性3：整棵树是BST
    bool leftBST = leftInfo == nullptr ? true : leftInfo->maxBSTSubTreeSize == leftInfo->allSize;
    bool rightBST = rightInfo == nullptr ? true : rightInfo->maxBSTSubTreeSize == rightInfo->allSize;
    if (leftBST && rightBST) {
    
        bool legalLeft = leftInfo == nullptr ? true : leftInfo->maxVal < x->value;
        bool legalRight = rightInfo == nullptr ? true : rightInfo->minVal > x->value;
        if (legalLeft && legalRight) {
    
            p3 = (leftInfo == nullptr ? 0 : leftInfo->allSize) + (rightInfo == nullptr ? 0 : rightInfo->allSize) + 1;
        }
    }
    
    int maxBSTSubTreeSize = max(max(p1, p2), p3);

    return new Info(maxBSTSubTreeSize, maxVal, minVal, allSize);
}

int largestBSTSubTree(TreeNode *root) {
    
    if (root == nullptr) return 0;

    return process(root)->maxBSTSubTreeSize;
}

Java 版

public class MaxSubBSTSize {
    
    public static class Node {
    
		public int value;
		public Node left;
		public Node right;

		public Node(int value) {
    
			this.value = value;
		}
	}

    public static int largestBSTSubtree(Node head) {
    
		if (head == null) {
    
			return 0;
		}
		return process(head).maxBSTSubTreeSize;
	}

    public static class Info {
    
        public int maxBSTSubTreeSize; //最大搜索二叉树的节点数
        public int allSize; //树的节点数
        public int max; //树的最大值
        public int min; //树的最小值

        public Info(int m, int a, int ma, int mi) {
    
            maxBSTSubTreeSize = m;
            allSize = a;
            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);

        int max = x.value;
        int min = x.value;
        int allSize = 1; //节点x本身
        if (leftInfo != null) {
    
            max = Math.max(leftInfo.max, max);
            min = Math.max(leftInfo.min, min);
            allSize += leftInfo.allSize;
        }
        if (rightInfo != null) {
    
            max = Math.max(rightInfo.max, max);
            min = Math.max(rightInfo.min, min);
            allSize += rightInfo.allSize;
        }

        int p1 = -1;
        if (leftInfo != null) {
     //可能性1：左树的maxBSTSubTreeSize
            p1 = leftInfo.maxBSTSubTreeSize;
        }
        int p2 = -1;
        if (rightInfo != null) {
     //可能性2
            p2 = rightInfo.maxBSTSubTreeSize;
        }
        //可能性3：X为根
        int p3 = -1;
        //左树是否为BST
        boolean leftBST = leftInfo == null ? true : (leftInfo.maxBSTSubTreeSize == leftInfo.allSize);
        //右树是否为BST
        boolean rightBST = rightInfo == null ? true : (rightInfo.maxBSTSubTreeSize == rightInfo.allSize);
        if (leftBST && rightBST) {
    
            //左树的max 是否 小于 x
            boolean leftMaxLessX = leftInfo == null ? true : (leftInfo.max < x.value);
            //右树的min 是否 大于 x
            boolean rightMinMoreX = rightInfo == null ? true : (rightInfo.min > x.value);
            if (leftMaxLessX && rightMinMoreX) {
    
                int leftSize = leftInfo == null ? 0 : leftInfo.allSize;
                int rightSize = rightInfo == null ? 0 : rightInfo.allSize;
                p3 = leftSize + rightSize + 1;
            }
        }

        int maxBSTSubTreeSize = Math.max(Math.max(p1, p2), p3);
         
        return new Info(maxBSTSubTreeSize, allSize, max, min);
    }
}