Computer >> 컴퓨터 >  >> 프로그램 작성 >> C++

C++에서 가장 큰 BST 하위 트리

<시간/>

이진 트리가 있다고 가정합니다. 가장 큰 부분은 가장 큰 수의 노드가 있는 하위 트리를 의미하는 가장 큰 하위 트리를 찾아야 합니다.

따라서 입력이 다음과 같으면

C++에서 가장 큰 BST 하위 트리

이 경우 가장 큰 BST 하위 트리가 강조 표시된 것이므로 출력은 3이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

  • 데이터라고 하는 하나의 구조를 정의합니다. 크기, maxVal, minVal 및 ok의 네 가지 값이 있습니다. ok는 참/거짓 값만 보유할 수 있습니다.

  • 해결(트리노드 * 노드)

  • 노드가 null이면 &miuns;

    • (0, infinity, -infinity, true)를 초기화하여 데이터를 반환합니다.

  • 왼쪽 :=해결(노드 왼쪽)

  • 왼쪽 :=해결(노드 오른쪽)

  • curr이라는 하나의 데이터 정의

  • curr.ok :=거짓

  • 노드의 val>=right.minVal이면 -

    • 통화 반환

  • 노드의 val이 <=left.maxVal이면 -

    • 통화 반환

  • left.ok가 true이고 right.ok가 true이면 -

    • curr.sz :=1 + left.sz + right.sz

    • curr.ok :=사실

    • curr.maxVal :=최대값(노드 및 right.maxVal의 값)

    • curr.minVal :=최대값(노드 및 left.minVal의 값)

  • curr.ok가 참이면 -

    • ret :=ret 및 curr.sz의 최대값

    • 통화 반환

  • 기본 방법에서 다음을 수행하십시오 -

  • ret :=0

  • 해결(루트)

  • 리턴 렛

예시

더 나은 이해를 위해 다음 구현을 살펴보겠습니다. −

#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
   int val;
   TreeNode *left, *right;
   TreeNode(int data){
      val = data;
      left = NULL;
      right = NULL;
   }
};
void insert(TreeNode **root, int val){
   queue<TreeNode*> q;
   q.push(*root);
   while(q.size()){
      TreeNode *temp = q.front();
      q.pop();
      if(!temp->left){
         if(val != NULL)
            temp->left = new TreeNode(val);
         else
            temp->left = new TreeNode(0);
         return;
      }
      else{
         q.push(temp->left);
      }
      if(!temp->right){
         if(val != NULL)
            temp->right = new TreeNode(val);
         else
            temp->right = new TreeNode(0);
         return;
      }
      else{
         q.push(temp->right);
      }
   }
}
TreeNode *make_tree(vector<int< v){
   TreeNode *root = new TreeNode(v[0]);
   for(int i = 1; i<v.size(); i++){
      insert(&root, v[i]);
   }
   return root;
}
struct Data{
   int sz;
   int maxVal;
   int minVal;
   bool ok;
   Data(){}
   Data(int a, int b, int c, bool d){
      sz = a;
      minVal = b;
      maxVal = c;
      ok = d;
   }
};
class Solution {
public:
   int ret;
   Data solve(TreeNode* node){
      if (!node)
         return Data(0, INT_MAX, INT_MIN, true);
      Data left = solve(node->left);
      Data right = solve(node->right);
      Data curr;
      curr.ok = false;
      if (node->val >= right.minVal) {
         return curr;
      }
      if (node->val <= left.maxVal) {
         return curr;
      }
      if (left.ok && right.ok) {
         curr.sz = 1 + left.sz + right.sz;
         curr.ok = true;
         curr.maxVal = max(node->val, right.maxVal);
         curr.minVal = min(node->val, left.minVal);
      }
      if (curr.ok)
         ret = max(ret, curr.sz);
      return curr;
   }
   int largestBSTSubtree(TreeNode* root){
      ret = 0;
      solve(root);
      return ret;
   }
};
main(){
   Solution ob;
   vector<int< v = {10,5,15,1,8,NULL,7};
   TreeNode *root= make_tree(v);
   cout << (ob.largestBSTSubtree(root));
}

입력

[10,5,15,1,8,null,7]

출력

3