Tìm tổng cây con lớn nhất trong cây nhị phân sao cho cây con đó cũng là BST trong C++

Trong bài toán này, chúng ta được cung cấp một cây nhị phân BT. Nhiệm vụ là viết chương trình tìm Tổng cây con lớn nhất trong Cây nhị phân sao cho cây con đó cũng là một Cây tìm kiếm nhị phân (BST).

Cây nhị phân có điều kiện đặc biệt: mỗi nút tối đa có hai nút con.

Cây tìm kiếm nhị phân (BST) là cây mà tất cả các nút tuân theo các thuộc tính:

• Giá trị khóa của cây con trái nhỏ hơn giá trị khóa của nút cha (gốc).
• Giá trị khóa của cây con phải lớn hơn hoặc bằng giá trị khóa của nút cha (gốc).

Ví dụ minh họa

Đầu vào

Đầu ra

32

Giải thích

Ở đây, ta có hai cây con là BST. Tổng của chúng:
7 + 3 + 22 = 32
6 + 5 + 17 = 28
Tổng lớn nhất = 32.

Phương pháp giải

Cách đơn giản: duyệt cây và kiểm tra tại mỗi nút xem các nút con của nó có thể tạo thành BST hay không. Tìm tổng tất cả các nút góp phần vào BST và trả về lớn nhất trong số các BSTSum tìm được.

Chương trình minh họa

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

int findMax(int a, int b) {
    if (a > b) return a;
    return b;
}

int findMin(int a, int b) {
    if (a > b) return b;
    return a;
}

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

struct treeVal {
    int maxVal;
    int minVal;
    bool isBST;
    int sum;
    int currMax;
};

treeVal CalcBSTSumTill(struct Node* root, int& maxsum) {
    if (root == NULL)
        return { -10000, 10000, true, 0, 0 };
    
    if (root->left == NULL && root->right == NULL) {
        maxsum = findMax(maxsum, root->data);
        return { root->data, root->data, true, root->data, maxsum };
    }
    
    treeVal LeftSTree = CalcBSTSumTill(root->left, maxsum);
    treeVal RightSTree = CalcBSTSumTill(root->right, maxsum);
    
    treeVal currTRee;
    
    if (LeftSTree.isBST && RightSTree.isBST && LeftSTree.maxVal < root->data && RightSTree.minVal > root->data) {
        currTRee.maxVal = findMax(root->data, findMax(LeftSTree.maxVal, RightSTree.maxVal));
        currTRee.minVal = findMin(root->data, findMin(LeftSTree.minVal, RightSTree.minVal));
        maxsum = findMax(maxsum, RightSTree.sum + root->data + LeftSTree.sum);
        currTRee.sum = RightSTree.sum + root->data + LeftSTree.sum;
        currTRee.currMax = maxsum;
        currTRee.isBST = true;
        return currTRee;
    }
    
    currTRee.isBST = false;
    currTRee.currMax = maxsum;
    currTRee.sum = RightSTree.sum + root->data + LeftSTree.sum;
    return currTRee;
}

int CalcMaxSumBST(struct Node* root) {
    int maxsum = -10000;
    return CalcBSTSumTill(root, maxsum).currMax;
}

int main() {
    struct Node* root = new Node(10);
    root->left = new Node(12);
    root->left->right = new Node(7);
    root->left->right->left = new Node(3);
    root->left->right->right = new Node(22);
    root->right = new Node(6);
    root->right->left = new Node(5);
    root->right->left->right = new Node(17);
    
    cout << "Tổng cây con lớn nhất trong cây nhị phân sao cho cây con cũng là BST là "
         << CalcMaxSumBST(root);
    return 0;
}

Đầu ra

Tổng cây con lớn nhất trong cây nhị phân sao cho cây con cũng là BST là 32