C++의 이진 트리에서 가장 큰 BST 변환-C++-php.cn

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

PHPz

풀어 주다： 2023-09-13 16:29:04

앞으로

882명이 탐색했습니다.

在C++中，将二叉树中的最大二叉搜索树（Largest BST in a Binary Tree）进行翻译

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

왼쪽 자식 노드는 부모 노드에 비해 작습니다.
오른쪽 자식 노드의 부모 노드는 자식 노드보다 큽니다. node

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

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

Enter

로그인 후 복사

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

Input

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

로그인 후 복사

Output

로그인 후 복사

노드 길이가 상위 트리의 길이보다 작은 하위 트리에는 크기가 최대 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;
}

로그인 후 복사