ผลรวมทรีย่อยสูงสุดในทรีไบนารี ซึ่งทรีย่อยยังเป็น BST ในโปรแกรม C++

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

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

Binary Search Tree เป็นต้นไม้ที่โหนดทั้งหมดเป็นไปตามคุณสมบัติที่กล่าวถึงด้านล่าง

• ค่าของคีย์ของทรีย่อยทางซ้ายนั้นน้อยกว่าค่าของคีย์ของโหนดหลัก (รูท)

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

มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน

อินพุต

ผลลัพธ์

32

คำอธิบาย

ที่นี่ เรามีทรีย่อยสองทรีย่อยที่เป็น BST ผลรวมคือ

7 + 3 + 22 = 32
6 + 5 + 17 = 28
Maximum = 32.

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

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

ตัวอย่าง

โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา

#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