資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法學在給定的二叉樹中查詢最大的 BST 子樹 - C++ 方法一
在這個問題中，我們給定一個二叉樹 BT。我們的任務是 *在給定的二叉樹中找到最大的 BST 子樹*。
二叉樹是一種特殊的資料結構，用於資料儲存。二叉樹有一個特殊條件，即每個節點最多可以有兩個子節點。
二叉搜尋樹 (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 BST is 5
更新於：2022年1月28日
221 次檢視
廣告