C++의 이진 트리에서 가장 큰 BST 변환

이진 트리에서 각 하위 노드에는 두 개의 노드(왼쪽 및 오른쪽)만 있습니다. 트리 구조는 단지 데이터를 표현한 것일 뿐입니다. BST(Binary Search Tree)는 이러한 조건을 만족하는 특별한 유형의 이진 트리입니다.

• 왼쪽 자식 노드는 부모 노드에 비해 작습니다.

• 오른쪽 자식 노드의 부모 노드는 자식 노드보다 큽니다. node

주어진 이진 트리에서 가장 큰 이진 검색 트리(BST)를 찾아야 한다고 가정합니다.

이 작업에서는 이진 트리에서 가장 큰 BST를 찾는 함수를 만듭니다. 이진 트리 자체가 BST이면 전체 이진 트리의 크기를 결정할 수 있습니다. 예를 들어 그림과 같이

Enter

  10
  /\
 5  15
 /\  \
1  8  7

을 입력하면 이 경우 강조 표시된 BST 하위 트리가 가장 큽니다. '3'은 하위 트리의 크기이므로 반환 값은 하위 트리의 크기입니다.

Input

    52
    / \
   37 67
   /\ / \
 12 27 57 77
          /\
         72 87

Output

5

노드 길이가 상위 트리의 길이보다 작은 하위 트리에는 크기가 최대 3개의 BST 노드가 있습니다.

주어진 이진 트리에서 최대 BST를 찾는 방법

각 노드 x에 대해 다음 사항이 유효한 경우 이진 트리는 BST입니다. 상위 노드의 데이터보다 적은 데이터를 가진 노드만 노드의 왼쪽 하위 트리에 나타납니다. 단 하나의 노드만이 상위 노드보다 더 많은 데이터를 가질 수 있습니다. 왼쪽 하위 트리와 오른쪽 하위 트리는 모두 이진 검색 트리(BST)로 표현되어야 합니다.

알고리즘은 다음과 같습니다.

우리는 이진 트리에서 재귀를 사용하여 중순 순회를 수행합니다. 현재 노드 "ROOT"에 대해 다음을 수행합니다.

• 유효한 BST의 루트인 경우 해당 크기를 반환합니다.

• 그렇지 않으면 왼쪽 및 오른쪽 하위 트리에서 최대 BST를 찾습니다.

Example

#include <bits/stdc++.h>
using namespace std;
struct Node {
   int data;
   struct Node *left;
   struct Node *right;
};
struct Node *
newNode (int data) {
   struct Node *node = new Node;
   node->data = data;
   node->left = node->right = NULL;
   return (node);
}
struct Detail {
   int size;
   int max;
   int min;
   int ans;
   bool isBST;
};
bool isBST (Node * root, int min, int max) {
   if (root == NULL) {
      return true;
   }
   if (root->data < min || root->data > max) {
      return false;
   }
   return isBST (root->left, min, root->data - 1) &&
   isBST (root->right, root->data + 1, max);
}
int size (Node * root) {
   if (root == NULL) {
      return 0;
   }
   return 1 + size (root->left) + size (root->right);
}
int largestBST (Node * root) {
   // Current Subtree is BST.
   if (isBST (root, INT_MIN, INT_MAX) == true) {
      return size (root);
   }
   // Find largest BST in left and right subtrees.
   return max (largestBST (root->left), largestBST (root->right));
}
int main () {
   struct Node *root = newNode (67);
   root->left = newNode (72);
   root->right = newNode (77); root->left->left = newNode (57);
   printf ("Size of the largest BST is %d", largestBST (root));
   return 0;
}

Output

Size of the largest BST is 2

Conclusion

이 질문에서 우리는 이진 트리와 이진 검색 트리가 무엇인지, 그리고 재귀의 도움을 받아 주어진 이진 트리에서 가장 큰 BST를 찾는 방법을 배웠습니다. 재귀의 도움으로 각 노드 아래의 하위 트리가 BST인지 확인하고 해당 값을 반환합니다.

위 내용은 C++의 이진 트리에서 가장 큰 BST 변환의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!