Returns the root node of the largest binary search subtree in a binary tree

1、 subject

Given the root node of a binary tree root, Return to the root node of the largest binary search subtree in the binary tree .

2、 analysis

Find the largest binary search subtree visible Returns the size of the largest binary search subtree in a binary tree , Here we are just looking for the root node , So in Info Add the information of a root node to the information body .

3、 Realization

C++ edition

/************************************************************************* > File Name: 039. Returns the root node of the largest binary search subtree of the binary tree .cpp > Author: Maureen > Mail: [email protected] > Created Time:  6、 ... and  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) {
    }
};


// Method 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;
}

// Method 2
class Info {
    
public:
    TreeNode *maxSubBSTRoot; // The root node of the largest binary search subtree 
    int maxSubBSTSize; // The maximum number of nodes in the binary search subtree 
    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);
        // possibility 1： The largest binary search subtree is on the left tree 
        maxSubBSTSize = leftInfo->maxSubBSTSize;
        maxSubBSTRoot = leftInfo->maxSubBSTRoot;
    } 

    if (rightInfo != nullptr) {
    
        maxVal = max(maxVal, rightInfo->maxVal);
        minVal = min(minVal, rightInfo->minVal);
        // possibility 2： The largest binary search subtree is on the right tree 
        if (rightInfo->maxSubBSTSize > maxSubBSTSize) {
    
            maxSubBSTSize = rightInfo->maxSubBSTSize;
            maxSubBSTRoot = rightInfo->maxSubBSTRoot;
        }
    }

    // possibility 3： The whole tree is 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 edition

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;
        }
    }

    // Method 1 ：
    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;
	}



    // Method 2 ： Recursive routine 
    public static Node maxSubBSTHead2(Node head) {
    
        if (head == null) return head;

        return process(head).maxSubBSTHead;
    }

    public static class Info {
    
        public Node maxSubBSTHead; // The root node of the maximum search subtree 
        public int maxSubBSTSize;// The maximum number of nodes to search the subtree 
        public int max; // Maximum 
        public int min; // minimum value 

        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;

        // Get the information of left and right trees 
        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) {
     // The left tree is not empty 
            // Update the latest value 
            max = Math.max(max, leftInfo.max);
            min = Math.min(min, leftInfo.min);
            // possibility 1： The largest search binary tree is on the left tree 
            maxSubBSTHead = leftInfo.maxSubBSTHead;
            maxSubBSTSize = leftInfo.maxSubBSTSize;
        }

        if (rightInfo != null) {
    
            max = Math.max(max, rightInfo.max);
            min = Math.min(min, rightInfo.min);
            // possibility 2： The largest search binary tree is on the right tree , The premise is that if the largest search subtree of the right tree size >  The largest search subtree of the left tree size
            if (rightInfo.maxSubBSTSize > maxSubBSTSize) {
    
                maxSubBSTHead = rightInfo.maxSubBSTHead;
                maxSubBSTSize = rightInfo.maxSubBSTSize;
            }
        }

        // possibility 3： The whole tree is the largest search binary tree 
        // If the root of the left and right subtrees happens to be the root of the largest search binary tree , that X The root binary tree is the largest search binary tree ,x For its root 
        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!");
	}
}