Tìm cây con BST lớn nhất trong cây nhị phân - Phần 1 C++

Cho cây nhị phân BT. Nhiệm vụ: tìm cây con BST (Binary Search Tree) lớn nhất.

Định nghĩa

• Cây nhị phân: mỗi nút tối đa 2 con.
• BST: nút con trái < nút cha ≤ nút con phải.

Phương pháp 1: Duyệt in-order + kiểm tra BST (O(n²))

Duyệt in-order, với mỗi nút kiểm tra cây con có phải BST không, trả về kích thước lớn nhất.

Phương pháp 2: Duyệt từ dưới lên (Bottom-up) O(n)

Duyệt post-order, tại mỗi nút theo dõi: có phải BST không, min/max của cây con, kích thước BST lớn nhất.

Ví dụ chương trình (Phương pháp 2)

#include<bits/stdc++.h> 
using namespace std; 

class Node{
public:
    int data;
    Node* left;
    Node* right;
    Node(int d){ data = d; left = right = NULL; }
};

int findLargestBSTSizeRec(Node* node, int *minVal, int *maxVal, int *maxBSTSize, bool *isBST) {
    if (!node){ *isBST = true; return 0; }
    int min = INT_MAX;
    bool left_flag = false, right_flag = false;
    int leftSize, rightSize;
    *maxVal = INT_MIN;
    leftSize = findLargestBSTSizeRec(node->left, minVal, maxVal, maxBSTSize, isBST);
    if (*isBST && node->data > *maxVal) left_flag = true;
    min = *minVal;
    *minVal = INT_MAX;
    rightSize = findLargestBSTSizeRec(node->right, minVal, maxVal, maxBSTSize, isBST);
    if (*isBST && node->data < *minVal) right_flag = true;
    if (min < *minVal) *minVal = min;
    *minVal = min(*minVal, node->data);
    *maxVal = max(*maxVal, node->data);
    if (left_flag && right_flag){
        if (leftSize + rightSize + 1 > *maxBSTSize) *maxBSTSize = leftSize + rightSize + 1;
        return leftSize + rightSize + 1;
    } else { *isBST = false; return 0; }
}

int findLargestBSTSize(Node* root){
    int min = INT_MAX, max = INT_MIN, largestBSTSize = 0;
    bool isBST = false;
    findLargestBSTSizeRec(root, &min, &max, &largestBSTSize, &isBST);
    return largestBSTSize;
}