Tổng lớn nhất của cây con là BST trong cây nhị phân C++

Mô tả bài toán

Cho cây nhị phân, tìm tổng lớn nhất của một cây con mà cây con đó cũng là một cây tìm kiếm nhị phân (BST).

Giải pháp (DFS + Thông tin cây con)

• Mỗi nút trả về struct Info chứa: max, min, isBST, sum, currmax (tổng BST lớn nhất trong cây con).
• Nút lá: là BST, sum = data, cập nhật maxsum.
• Nút nội bộ: nếu cây con trái và phải đều là BST, và L.max < root->data < R.min → nút hiện tại là BST.
  • Cập nhật sum = L.sum + root->data + R.sum, maxsum.
• Ngược lại, đánh dấu isBST = false, vẫn truyền maxsum lên cha.

Ví dụ minh họa

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

struct Node {
    Node *left, *right;
    int data;
    Node(int data) { this->data = data; left = right = NULL; }
};

struct Info {
    int max, min;
    bool isBST;
    int sum, currmax;
};

Info MaxSumBSTUtil(Node* root, int& maxsum) {
    if (!root) return {INT_MIN, INT_MAX, true, 0, 0};
    if (!root->left && !root->right) {
        maxsum = max(maxsum, root->data);
        return {root->data, root->data, true, root->data, maxsum};
    }
    Info L = MaxSumBSTUtil(root->left, maxsum);
    Info R = MaxSumBSTUtil(root->right, maxsum);
    Info BST;
    if (L.isBST && R.isBST && L.max < root->data && R.min > root->data) {
        BST.max = max(root->data, max(L.max, R.max));
        BST.min = min(root->data, min(L.min, R.min));
        maxsum = max(maxsum, R.sum + root->data + L.sum);
        BST.sum = R.sum + root->data + L.sum;
        BST.currmax = maxsum;
        BST.isBST = true;
        return BST;
    }
    BST.isBST = false;
    BST.currmax = maxsum;
    BST.sum = R.sum + root->data + L.sum;
    return BST;
}

int MaxSumBST(Node* root) {
    int maxsum = INT_MIN;
    return MaxSumBSTUtil(root, maxsum).currmax;
}

int main() {
    Node* root = new Node(5);
    root->left = new Node(14);
    root->right = new Node(3);
    root->left->left = new Node(6);
    root->right->right = new Node(7);
    root->left->left->left = new Node(9);
    root->left->left->right = new Node(1);
    cout << MaxSumBST(root);
    return 0;
}

Đầu ra

10