ผลรวมสูงสุดของ BST ในต้นไม้แบบทวิภาคใน C++

คำอธิบายโจทย์

กำหนดให้มีต้นไม้แบบทวิภาค (binary tree) ให้หาผลรวมสูงสุดของโหนดทั้งหมดใน subtree ใดๆ ที่เป็น Binary Search Tree (BST) ได้

ตัวอย่าง

ผลลัพธ์คือ 20 ซึ่งเป็นผลรวมของโหนดใน BST ที่เลือก

วิธีแก้ปัญหา

ใช้ Post-order traversal (DFS) พร้อมเก็บข้อมูลของแต่ละ subtree:

• sz: ขนาดของ subtree
• minVal: ค่าต่ำสุดใน subtree
• maxVal: ค่าสูงสุดใน subtree
• ok: เป็น BST หรือไม่
• sum: ผลรวมค่าโหนดใน subtree

เงื่อนไข BST: ค่าโหนดปัจจุบัน > maxVal ของ subtree ซ้าย และ < minVal ของ subtree ขวา และทั้งสอง subtree ต้องเป็น BST ด้วย

การทำงานของโค้ด

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

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

struct Data {
    int sz, maxVal, 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(ret, curr.sum);
            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;
    }
};

// ฟังก์ชันสร้างต้นไม้สำหรับทดสอบ
void insert(TreeNode** root, int val) { ... }
TreeNode* make_tree(vector<int> v) { ... }

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;
}

อินพุต

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

เอาต์พุต

20