ผลรวมซับทรีสูงสุดในต้นไม้แบบทวิภาคที่ซับทรีเป็น BST ในโปรแกรม C++

ในปัญหานี้ เราได้รับต้นไม้แบบทวิภาค BT ภารกิจของเราคือสร้างโปรแกรมเพื่อหาผลรวมซับทรีสูงสุดในต้นไม้แบบทวิภาคที่ซับทรีเป็น BST ด้วย

ต้นไม้แบบทวิภาค (Binary Tree) มีเงื่อนไขพิเศษคือแต่ละโหนดสามารถมีลูกได้สูงสุดสองตัว

ต้นไม้ค้นหาแบบทวิภาค (Binary Search Tree) เป็นต้นไม้ที่โหนดทั้งหมดปฏิบัติตามคุณสมบัติด้านล่าง

• ค่าของคีย์ซับทรีซ้าย น้อยกว่าค่าของคีย์โหนดพ่อ (ราก)
• ค่าของคีย์ซับทรีขวา มากกว่าหรือเท่ากับค่าของคีย์โหนดพ่อ (ราก)

ตัวอย่าง

อินพุต

เอาต์พุต

32

คำอธิบาย

ที่นี่เรามีซับทรีสองอันที่เป็น BST ผลรวมของพวกเขาคือ

7 + 3 + 22 = 32 
6 + 5 + 17 = 28 
สูงสุด = 32

แนวทางแก้ปัญหา

วิธีแก้ที่ง่ายคือการเดินทางผ่านโครงสร้างข้อมูลต้นไม้ แล้วตรวจสอบที่แต่ละโหนดว่าลูกของมันสามารถสร้างต้นไม้ค้นหาแบบทวิภาคได้หรือไม่ หากเราพบผลรวมของโหนดทั้งหมดที่มีส่วนทำให้เป็น BST แล้วคืนค่าสูงสุดของ BSTSum ทั้งหมดที่พบ

ตัวอย่างโค้ด

โปรแกรมสำหรับแสดงการทำงานของวิธีแก้ปัญหาของเรา

#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 << "The maximum sub-tree sum in a Binary Tree such that the sub-tree is also a BST is " << CalcMaxSumBST(root); 
    return 0; 
}

เอาต์พุต

The maximum sub-tree sum in a Binary Tree such that the sub-tree is also a BST is 32