Largest BST Subtree - Cây con BST lớn nhất

Cho cây nhị phân, tìm cây con là BST có số nút lớn nhất.

Ví dụ: cây cho trước → kết quả 3 (cây con BST lớn nhất có 3 nút).

Giải thuật (DFS post-order với thông tin subtree)

Mỗi nút trả về: kích thước, giá trị min, max, và cờ isBST. Nút là BST nếu: cây con trái và phải đều là BST, node.val > left.max, node.val < right.min. Cập nhật kết quả toàn cục khi tìm thấy BST hợp lệ.

Cài đặt C++

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

class TreeNode {
public:
    int val;
    TreeNode *left, *right;
    TreeNode(int data) { val = data; left = right = NULL; }
};

struct Data {
    int sz;
    int maxVal;
    int minVal;
    bool ok;
    Data() {}
    Data(int a, int b, int c, bool d) : sz(a), minVal(b), maxVal(c), ok(d) {}
};

class Solution {
public:
    int ret = 0;

    Data solve(TreeNode* node) {
        if (!node) return Data(0, INT_MAX, INT_MIN, true);
        Data left = solve(node->left);
        Data right = solve(node->right);
        Data curr;
        curr.ok = false;

        if (node->val >= right.minVal) return curr;
        if (node->val <= left.maxVal) return curr;

        if (left.ok && right.ok) {
            curr.sz = 1 + left.sz + right.sz;
            curr.ok = true;
            curr.maxVal = max(node->val, right.maxVal);
            curr.minVal = min(node->val, left.minVal);
        }
        if (curr.ok) ret = max(ret, curr.sz);
        return curr;
    }

    int largestBSTSubtree(TreeNode* root) {
        ret = 0;
        solve(root);
        return ret;
    }
};

int main() {
    Solution ob;
    // Tree construction omitted
    return 0;
}

Đầu vào

[10,5,15,1,8,null,7]

Đầu ra

3