Trong bài toán này, chúng ta được cung cấp một cây nhị phân BT. Nhiệm vụ của chúng tôi là tìm cây con BST lớn nhất trong Cây nhị phân đã cho .
Cây nhị phân là một cấu trúc dữ liệu đặc biệt được sử dụng cho mục đích lưu trữ dữ liệu. Cây nhị phân có một điều kiện đặc biệt là mỗi nút có thể có tối đa hai nút con.
Cây tìm kiếm nhị phân (BST) là một cây trong đó tất cả các nút tuân theo các thuộc tính được đề cập bên dưới -
-
Giá trị của khóa của cây con bên trái nhỏ hơn giá trị của khóa của nút cha (gốc) của nó.
-
Giá trị của khóa của cây con bên phải lớn hơn hoặc bằng giá trị của khóa của nút cha (gốc) của nó.
Hãy lấy một ví dụ để hiểu vấn đề,
Đầu vào:
Đầu ra:3
Giải thích
Full binary tree is a BST.
Phương pháp tiếp cận giải pháp
Một giải pháp đơn giản cho vấn đề là thực hiện chuyển động theo thứ tự của cây. Và đối với mỗi nút của cây, hãy kiểm tra xem các cây con của nó có phải là BST hay không. Cuối cùng, trả về kích thước của cây con lớn nhất là BST.
Ví dụ
Chương trình minh họa hoạt động của giải pháp của chúng tôi
#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;
} Đầu ra
The size of the largest possible BST is 5
Cách tiếp cận khác
Một giải pháp khác cho vấn đề là bằng cách duyệt cây từ dưới lên và kiểm tra xem nó có phải là BST hay không bằng cách sử dụng các nút con của nó. Đối với nút này, chúng tôi sẽ theo dõi
Nếu nó là một BST hay không.
-
Giá trị của phần tử tối đa, trong trường hợp của Cây con bên trái.
-
Phần tử tối thiểu, trong trường hợp cây con bên phải. Các giá trị này cần được so sánh với nút hiện tại để kiểm tra BST.
Ngoài ra, kích thước của BST lớn nhất sẽ được cập nhật bằng cách kiểm tra với kích thước BST hiện tại.
Ví dụ
#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;
} Đầu ra
The Size of the largest BST is 5