C++のバイナリツリーで最大のBST

二分木では、各子ノードには2つのノード（左と右）しかありません。ツリー構造は、単にデータを表現したものです。二分探索木（BST）は、これらの条件を満たす特殊なタイプの二分木です-

• 親と比較して、左側の子ノードは小さくなっています

• 右の子の親ノードが子ノードよりも大きい

二分木が与えられ、その中で最大の二分探索木（BST）が何であるかを見つけることになっていると仮定します。

このタスクでは、二分木で最大のBSTを見つける関数を作成します。二分木自体がBSTである場合、二分木全体のサイズを決定することができます。例として-

入力

      10
      /\
    5    15
   /\ \
1 8 7

示されているように、この場合、強調表示されているBSTサブツリーが最大です。 「3」はサブツリーのサイズであるため、戻り値はサブツリーのサイズです。

入力

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

出力

5

親ノードの長さよりも短いノードを持つサブツリーには、最大3つのサイズのBSTノードがあります。

指定された二分木で最大のBSTを見つけるためのアプローチ

次の点が有効な場合、すべてのノードxについて、二分木はBSTになります。データが親ノードのデータよりも少ないノードのみが、ノードの左側のサブツリーに表示されます。親ノードよりも多くのデータを持つノードは1つだけです。左と右の両方のサブツリーは、二分探索木（BST）によって特徴付けられる必要があります。

アルゴリズムは-になります

二分木のルートから開始し、再帰を使用して順序どおりにトラバーサルを実行します。現在のノード「ROOT」に対して、次のことを行います-

• 有効なBSTのルートである場合は、そのサイズを返します。

• それ以外の場合は、左右のサブツリーで最大のBSTが見つかります。

例

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

出力

Size of the largest BST is 2

結論

この問題では、二分木と二分探索木とは何か、そして再帰の助けを借りて、与えられた二分木の中で最大のBSTを見つける方法を学びました。再帰の助けを借りて、すべてのノードの下のサブツリーがBSTであるかどうかを調べ、それに応じて値を返します。