ในปัญหานี้ เราได้รับไบนารีทรี BT งานของเราคือ ค้นหาทรีย่อย BST ที่ใหญ่ที่สุดในทรีไบนารีที่กำหนด .
Binary Tree เป็นโครงสร้างข้อมูลพิเศษที่ใช้เพื่อการจัดเก็บข้อมูล ต้นไม้ไบนารีมีเงื่อนไขพิเศษที่แต่ละโหนดสามารถมีลูกได้สูงสุดสองคน
Binary Search Tree (BST) เป็นต้นไม้ที่โหนดทั้งหมดเป็นไปตามคุณสมบัติที่กล่าวถึงด้านล่าง -
-
ค่าของคีย์ของทรีย่อยทางซ้ายนั้นน้อยกว่าค่าของคีย์ของโหนดหลัก (รูท)
-
ค่าของคีย์ของทรีย่อยทางขวามากกว่าหรือเท่ากับค่าของคีย์ของโหนดหลัก (รูท)
มาดูตัวอย่างเพื่อทำความเข้าใจปัญหากัน
ข้อมูลเข้า :
เอาท์พุต :3
คำอธิบาย
Full binary tree is a BST.
แนวทางการแก้ปัญหา
วิธีแก้ปัญหาอย่างง่ายคือดำเนินการสำรวจต้นไม้ตามลำดับ และสำหรับแต่ละโหนดของทรี ให้ตรวจสอบว่าทรีย่อยของมันคือ BST หรือไม่ สุดท้ายให้คืนค่าขนาดของทรีย่อยที่ใหญ่ที่สุดซึ่งเป็น BST
ตัวอย่าง
โปรแกรมเพื่อแสดงการทำงานของโซลูชันของเรา
#include<bits/stdc++.h>
using namespace std;
class node{
public:
int data;
node* left;
node* right;
node(int data){
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
int findTreeSize(node* node) {
if (node == NULL)
return 0;
else
return(findTreeSize(node->left) + findTreeSize(node->right) + 1);
}
int isBSTree(struct node* node) {
if (node == NULL)
return 1;
if (node->left != NULL && node->left->data > node->data)
return 0;
if (node->right != NULL && node->right->data < node->data)
return 0;
if (!isBSTree(node->left) || !isBSTree(node->right))
return 0;
return 1;
}
int findlargestBSTSize(struct node *root) {
if (isBSTree(root)){
return findTreeSize(root);
}
else
return max(findlargestBSTSize(root->left), findlargestBSTSize(root->right));
}
int main() {
node *root = new node(5);
root->left = new node(2);
root->right = new node(8);
root->left->left = new node(1);
root->left->right = new node(4);
cout<<"The size of the largest possible BST is "<<findlargestBSTSize(root);
return 0;
} ผลลัพธ์
The size of the largest possible BST is 5
แนวทางอื่น
อีกวิธีแก้ไขปัญหาคือโดยการสำรวจทรีจากด้านล่างและตรวจสอบว่าเป็น BST โดยใช้โหนดย่อยหรือไม่ สำหรับโหนดนี้ เราจะคอยติดตาม
ถ้าเป็น BST หรือเปล่า
-
ค่าขององค์ประกอบสูงสุดในกรณีของทรีย่อยด้านซ้าย
-
องค์ประกอบขั้นต่ำ ในกรณีของทรีย่อยด้านขวา ค่าเหล่านี้จำเป็นต้องเปรียบเทียบกับโหนดปัจจุบันสำหรับการตรวจสอบ BST
นอกจากนี้ ขนาดของ BST ที่ใหญ่ที่สุดจะได้รับการอัปเดตโดยการตรวจสอบกับขนาด BST ปัจจุบัน
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
class node{
public:
int data;
node* left;
node* right;
node(int data){
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
int findlargestBSTSizeRec(node* node, int *minValRsubTree, int *maxValLsubTree, int *maxBSTSize, bool *isBSTree) {
if (node == NULL){
*isBSTree = true;
return 0;
}
int min = INT_MAX;
bool left_flag = false;
bool right_flag = false;
int leftSubtreeSize,rightSubTreeSize;
*maxValLsubTree = INT_MIN;
leftSubtreeSize = findlargestBSTSizeRec(node->left, minValRsubTree, maxValLsubTree, maxBSTSize, isBSTree);
if (*isBSTree == true && node->data > *maxValLsubTree)
left_flag = true;
min = *minValRsubTree;
*minValRsubTree = INT_MAX;
rightSubTreeSize = findlargestBSTSizeRec(node->right, minValRsubTree, maxValLsubTree, maxBSTSize, isBSTree);
if (*isBSTree == true && node->data < *minValRsubTree)
right_flag = true;
if (min < *minValRsubTree)
*minValRsubTree = min;
if (node->data < *minValRsubTree)
*minValRsubTree = node->data;
if (node->data > *maxValLsubTree)
*maxValLsubTree = node->data;
if(left_flag && right_flag){
if (leftSubtreeSize + rightSubTreeSize + 1 > *maxBSTSize)
*maxBSTSize = (leftSubtreeSize + rightSubTreeSize + 1);
return (leftSubtreeSize + rightSubTreeSize + 1);
}
else{
*isBSTree = false;
return 0;
}
}
int findlargestBSTSize(node* node){
int min = INT_MAX;
int max = INT_MIN;
int largestBSTSize = 0;
bool isBST = false;
findlargestBSTSizeRec(node, &min, &max, &largestBSTSize, &isBST);
return largestBSTSize;
}
int main(){
node *root = new node(5);
root->left = new node(2);
root->right = new node(8);
root->left->left = new node(1);
root->left->right = new node(4);
cout<<"The Size of the largest BST is "<<findlargestBSTSize(root);
return 0;
} ผลลัพธ์
The size of the largest possible BST is 5
