二分木がBSTであるかどうかをチェックするプログラム


難易度 簡単に
よく聞かれる アコライト Adobe Amazon (アマゾン) ブーメランコマース ファクトセット GreyOrange MakeMyTrip マイクロソフト オラクル OYOルーム クアルコム Snapdeal ヴイエムウェア ウォルマート・ラボ ウッカー
二分探索木 二分木

問題文

「二分木がBSTであるかどうかをチェックするプログラム」は、二分木が与えられていることを示しており、二分木が二分探索木の特性を満たしているかどうかを確認する必要があります。 したがって、二分木には次のプロパティがあります。 

  1. 左側のサブツリーには、ルートよりも小さい値のノードが必要です。
  2. 右側のサブツリーには、ルートより大きいデータを持つノードが含まれている必要があります
  3. 左右のサブツリー自体は二分探索木である必要があります。つまり、それら自体が二分探索木のプロパティに従う必要があります。

入力

二分木がBSTであるかどうかをチェックするプログラム

YES

説明:指定されたツリーは、バイナリ検索ツリーのすべてのプロパティに従います。 左側のサブツリーのすべてのノードは、ルートの値よりも小さくなっています。 また、右側のサブツリーについても同じことが言えます。ノードの値はルートよりも大きくなります。 そして、左のサブツリーと右のサブツリー自体は、BSTのプロパティに従います。

入力

NO

説明:ツリーはのプロパティに従いません BST、左側のサブツリーのすべてのノードの値はルートよりも小さい必要があります。

二分木がBSTであるかどうかをチェックするプログラムのアプローチ

素朴なアプローチ (間違ったアプローチ)

ここでは、左側のサブツリーのルートの値がルート値よりも小さいかどうかをチェックするプログラムを作成するだけです。 そして、右側のサブツリーのルートは、ルートよりも大きな値を持っています。 次に、左右のサブツリーを再帰的にチェックします。 しかし、左側のサブツリーのルートがルートよりも小さい場合でも、このアプローチは間違っています。 左側のサブツリーに、ルートと比較して値が大きいノードが存在する場合があります。 右のサブツリーについても同様です。 したがって、その場合、このアプローチは失敗します。

指定されたツリー(画像)でアルゴリズムを実行します。 アルゴリズムが指定された二分木がBSTであることを返す場合でも、あなたは見つけるでしょう。 ただし、右側のサブツリーの1は2より小さいため、他のアプローチを見つける必要があります。

効率的なアプローチ (正しいアプローチ)

最小と最大の1つの変数を使用して、左右のサブツリーの範囲を定義します。 これにより、左側のサブツリーの要素が特定の範囲内にあるかどうかがわかります。 サブツリーを変更し続けると、この範囲は変更され続けます。 この方法は、素朴なアプローチで直面する欠陥を取り除くために使用されます。 そこでは、左側のサブツリーのすべての要素がルートよりも小さくなることを保証できませんでした。 そして、右側のサブツリーのすべての要素はルートよりも大きくなります。 最初に、整数の最小値として最小値を設定し、整数の最大値として最大値を設定して、BSTチェッカーを呼び出します。 これは、ルートの値を満たす必要がある範囲だからです。 次に、左側のサブツリーの最大値をルートの値-XNUMXとして更新し、右側のサブツリーの最大値をルートの値として設定します。 次に、最小値と最大値を適切に設定し、左右のサブツリーの関数を再帰的に呼び出します。

コード

二分木がBSTであるかどうかをチェックするC ++プログラム

#include<bits/stdc++.h>
using namespace std;

struct node{
    int data;
    node *left;
    node *right;
} ;

node* create(int data){
    node *tmp = new node();
    tmp->data = data;
    tmp->left = tmp->right = NULL;
}

bool isThisBST(node* root, int minimum, int maximum)
{
    // if there is no tree
    if(!root)
        return true;

    // the root should be in the range defined by [minimum, maximum]
    if(root->data < minimum || root->data > maximum)
        return false;
    // if the root satisfies the value then we recursively check the same for left and right subtree
    // we set the minimum and maximum for left and right subtrees accordingly.
    return isThisBST(root->left, minimum, root->data-1) && isThisBST(root->right, root->data+1, maximum);
}

int main()
{
    node *root = create(2);
    root->left = create(1);
    root->right = create(4);
    root->right->left = create(3);
    root->right->right = create(5);

    bool isBST = isThisBST(root, INT_MIN, INT_MAX);
    cout<<((isBST == true) ? "YES" : "NO");
    return 0;
}
YES

二分木がBSTであるかどうかをチェックするJavaプログラム

// Class that denote a node of the tree
class Node 
{ 
    int data; 
    Node left, right; 
  
    public Node(int data) 
    { 
        this.data = data;
        left = right = null; 
    } 
} 

class Tree 
{ 
    static Node root; 
  
  // return true if the tree is BST else return false
    static boolean isThisBST(Node root, int minimum, int maximum)
    { 
        // if there is no tree
      if(root == null)
          return true;
  
      // the root should be in the range defined by [minimum, maximum]
      if(root.data < minimum || root.data > maximum)
          return false;
      // if the root satisfies the value then we recursively check the same for left and right subtree
      // we set the minimum and maximum for left and right subtrees accordingly.
      return isThisBST(root.left, minimum, root.data-1) && isThisBST(root.right, root.data+1, maximum);
    } 
  
    public static void main(String args[]) 
    { 
        Tree tree = new Tree(); 
        tree.root = new Node(2); 
        tree.root.left = new Node(1); 
        tree.root.right = new Node(4); 
        tree.root.right.left = new Node(3); 
        tree.root.right.right = new Node(5); 
  
        boolean isBST = isThisBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
    	System.out.print((isBST == true) ? "YES" : "NO");
    }
}
YES

複雑さの分析

時間の複雑さ

オン)、私たちは木を横断しただけだからです。 また、XNUMX回のトラバーサルでは、線形の時間計算量が必要になります。

スペースの複雑さ

O(1) 一定数の変数のみを使用したため一定のスペースですが、ツリーにはN個のノードがあるため、プログラム全体でO(N)を取ります。