Returns the size of the largest binary search subtree in a binary tree

1、 subject

Given the root node of a binary tree root, Returns the size of the largest binary search subtree in this binary tree

2、 analysis

A binary tree may not be a binary search tree , But its subtree may be a binary search tree .

Recursive routines using binary trees .

① The goal is ： seek X The number of nodes of the maximum binary search subtree of the binary tree of the root node .

② possibility ：

1）X Do not do the root of the situation ：
（1） The result is on the left tree , On the left tree maxBSTSubTreeSize;
（2） The result is on the right tree , On the right tree maxBSTSubTreeSize;

2）X The situation of rooting . Then the whole tree is BST, It needs to be proved that the tree is BST, You need to get information from the left and right trees ：（1） Is the left tree BST;
（2） Is the right tree BST;
（3） Left tree max < x;
（4） Right tree min > x;
（5） Left tree size + Right tree size + 1.

Sort out the union of all conditions to get the required information ：
（1）maxBSTSubTreeSize;
（2） Is it BST
（3）max
（4）min
（5）size
But it can be simplified , If maxBSTSubTreeSize and size They are equal. , Then the whole tree is BST, therefore （2） This information can be omitted .

3、 Realization

C++ edition

// Verification has not been submitted yet 
/************************************************************************* > File Name: 038. Returns the size of the largest binary search subtree of a binary tree .cpp > Author: Maureen > Mail: [email protected] > Created Time:  6、 ... and  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;// The maximum number of nodes to search a binary tree 
    int maxVal; // The maximum value of a tree 
    int minVal; // The minimum value of a tree 
    int allSize; // The number of nodes in the tree 

    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;
        // possibility 1： The answer is in the left tree 
        p1 = leftInfo->maxBSTSubTreeSize;
    }

    if (rightInfo != nullptr) {
    
        maxVal = max(maxVal, rightInfo->maxVal);
        minVal = min(minVal, rightInfo->minVal);
        allSize += rightInfo->allSize;
        // possibility 2： The answer is in the right tree 
        p2 = rightInfo->maxBSTSubTreeSize;
    }
    
    // possibility 3： The whole tree is 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 edition

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; // The maximum number of nodes to search a binary tree 
        public int allSize; // The number of nodes in the tree 
        public int max; // The maximum value of a tree 
        public int min; // The minimum value of a tree 

        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; // node x In itself 
        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) {
     // possibility 1： Left tree maxBSTSubTreeSize
            p1 = leftInfo.maxBSTSubTreeSize;
        }
        int p2 = -1;
        if (rightInfo != null) {
     // possibility 2
            p2 = rightInfo.maxBSTSubTreeSize;
        }
        // possibility 3：X Root 
        int p3 = -1;
        // Whether the left tree is BST
        boolean leftBST = leftInfo == null ? true : (leftInfo.maxBSTSubTreeSize == leftInfo.allSize);
        // Whether the right tree is BST
        boolean rightBST = rightInfo == null ? true : (rightInfo.maxBSTSubTreeSize == rightInfo.allSize);
        if (leftBST && rightBST) {
    
            // Left tree max  whether   Less than  x
            boolean leftMaxLessX = leftInfo == null ? true : (leftInfo.max < x.value);
            // Right tree min  whether   Greater than  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);
    }
}