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

Cho một cây nhị phân gốc, ta cần tìm tổng lớn nhất của tất cả các nút của bất kỳ cây con nào cũng là một Cây Tìm Kiếm Nhị Phân (BST).

Ví dụ, với đầu vào như hình:

Đầu ra sẽ là 20, là tổng của tất cả các nút trong BST được chọn.

Giải pháp

Các bước thực hiện:

Tạo cấu trúc Data chứa: sz (kích thước), maxVal, minVal, ok (đánh dấu BST hợp lệ), sum (tổng giá trị)
Khởi tạo ret = 0
Định nghĩa hàm solve() nhận gốc cây con
Nếu node rỗng hoặc giá trị 0: trả về Data(0, INF, -INF, true)
Gọi đệ quy cho cây con trái và phải
Kiểm tra điều kiện BST: node->val < right.minVal và node->val > left.maxVal
Nếu cả hai cây con đều là BST hợp lệ: cập nhật sum, sz, ok, maxVal, minVal cho node hiện tại; cập nhật ret = max(ret, curr.sum)
Trả về Data của node hiện tại
Từ main: gọi solve(root) và trả về ret

Ví dụ mã C++

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

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

void insert(TreeNode **root, int val) { 
    queue<TreeNode*> q; 
    q.push(*root); 
    while(q.size()) { 
        TreeNode *temp = q.front(); 
        q.pop(); 
        if(!temp->left) { 
            if(val != NULL) temp->left = new TreeNode(val); 
            else temp->left = new TreeNode(0); 
            return; 
        } else q.push(temp->left); 
        
        if(!temp->right) { 
            if(val != NULL) temp->right = new TreeNode(val); 
            else temp->right = new TreeNode(0); 
            return; 
        } else q.push(temp->right); 
    } 
} 

TreeNode *make_tree(vector<int> v) { 
    TreeNode *root = new TreeNode(v[0]); 
    for(int i = 1; i < v.size(); i++) insert(&root, v[i]); 
    return root; 
} 

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

class Solution { 
public: 
    int ret = 0; 
    
    Data solve(TreeNode* node) { 
        if (!node || node->val == 0) 
            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.sum = node->val + left.sum + right.sum; 
            ret = max(curr.sum, ret); 
            curr.sz = 1 + left.sz + right.sz; 
            curr.ok = true; 
            curr.maxVal = max(node->val, right.maxVal); 
            curr.minVal = min(node->val, left.minVal); 
        } 
        return curr; 
    } 
    
    int maxSumBST(TreeNode* root) { 
        ret = 0; 
        solve(root); 
        return ret; 
    } 
}; 

int main() { 
    Solution ob; 
    vector<int> v = {1,4,3,2,4,2,5,NULL,NULL,NULL,NULL,NULL,NULL,4,6}; 
    TreeNode *root = make_tree(v); 
    cout << (ob.maxSumBST(root)); 
    return 0; 
}

Đầu vào

{1,4,3,2,4,2,5,NULL,NULL,NULL,NULL,NULL,NULL,4,6}