BST con lớn nhất trong C ++

Giả sử chúng ta có một cây nhị phân; chúng ta phải tìm cây con lớn nhất trong đó lớn nhất có nghĩa là cây con có số nút lớn nhất trong đó.

Vì vậy, nếu đầu vào giống như,

thì đầu ra sẽ là 3, vì Cây con BST lớn nhất, trong trường hợp này, là cây được đánh dấu.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

Xác định một cấu trúc được gọi là dữ liệu, sẽ có bốn giá trị, size, maxVal, minVal và ok, ok chỉ có thể chứa các giá trị true / false
giải quyết (nút TreeNode *)
nếu nút là null, thì &miuns;
- trả về Dữ liệu bằng cách khởi tạo (0, infinity, -infinity, true)
left:=giải quyết (bên trái của nút)
left:=giải quyết (bên phải của nút)
Xác định một dữ liệu được gọi là curr
curr.ok:=false
nếu val của nút> =right.minVal, thì -
- trả lại curr
nếu val của nút <=left.maxVal, thì -
- trả lại curr
nếu left.ok là true và right.ok là true, thì -
- curr.sz:=1 + left.sz + right.sz
- curr.ok:=true
- curr.maxVal:=tối đa của (val của nút và bên phải.maxVal)
- curr.minVal:=tối đa của (val của nút và left.minVal)
nếu curr.ok là true, thì -
- ret:=tối đa của ret và curr.sz
- trả lại curr
Từ phương thức chính, thực hiện như sau -
ret:=0
giải quyết (root)
trả lại ret

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

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

BST con lớn nhất trong C ++

Ví dụ

Đầu vào

Đầu ra