주어진 이진 트리에서 가장 큰 BST 하위 트리 찾기

<시간/>

이 문제에서는 이진 트리 BT가 주어집니다. 우리의 임무는 주어진 이진 트리에서 가장 큰 BST 하위 트리를 찾는 것입니다. .

이진 트리는 데이터 저장 목적으로 사용되는 특수 데이터 구조입니다. 바이너리 트리에는 각 노드가 최대 2개의 자식을 가질 수 있다는 특수한 조건이 있습니다.

BST(Binary Search Tree)는 모든 노드가 아래에 언급된 속성을 따르는 트리입니다 -

왼쪽 하위 트리의 키 값이 상위(루트) 노드의 키 값보다 작습니다.
오른쪽 하위 트리의 키 값이 상위(루트) 노드의 키 값보다 크거나 같습니다.

문제를 이해하기 위해 예를 들어 보겠습니다.

입력:

주어진 이진 트리에서 가장 큰 BST 하위 트리 찾기 - C++에서 1로 설정

출력 :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인지 아닌지.

왼쪽 subTree의 경우 최대 요소 값입니다.
오른쪽 subTree의 경우 최소 요소입니다. 이 값은 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